The speed of sound depends on the rigidity (or compressibility for liquids and gases) and the density of the medium it is traveling through.
A more rigid (less compressible) medium has stronger attraction and repulsion between its particles, so disturbing one particle will have a greater effect on other neighboring particles. Any disturbance is then transmitted from particle to particle at a faster rate, resulting in a greater sound speed. Imagine this as a spring that connects two individual particles, then the more rigid the medium, the stiffer that spring will be.
The more dense the medium, the more mass will have to be disturbed in order to travel the same distance, requiring more energy. This increased resistance to disturbance leads to a lower sound speed. When measuring sound speeds, you must take note of the temperature and pressure, as these will affect the density of the medium. For most media, the density will increase as the pressure increases but decrease as the temperature increases.
In general, gases are much more compressible than solids and liquids, so their sound speeds are much lower. At a temperature of 20°C and at atmospheric pressure, the speed of sound in air is 343 m/s, while in steel it is 5940 m/s. Imagine standing 1 km down a train track from your friend while they hit the steel rail with a hammer. It would take this sound 3 seconds to reach you through the air, but if you were to put your ear against the rail, you would hear the sound after only 0.17 seconds!
As a sound wave enters a different medium and its speed, v, changes, its frequency, f, remains unaffected. Using the wave equation, v = f λ, we can see that this means its wavelength, λ, must also change.