Sound waves travel fastest in solids because solids are the most dense state of matter.
Sound waves travel by vibrating particles. The closer the particles are to each other, the easier it is for them to bump into each other and pass on the vibration.
Gas particles, like air, are very spread apart, and as such, it takes the particles longer to travel between each other to pass on the vibrations. Water particles are slightly closer together, meaning it takes even less time for them to transmit vibrations. Finally, particles in a solid are locked together side-by-side, nearly touching each other, meaning that the passage of sound vibrations between them is nearly instantaneous.