The sound problem

Sound wave propagation speed depends on the material. The frequency of the wave is source dependent so that has no bearing on the speed. What does affect the speed of sound are the material properties such as density, bulk modulus etc. Essentially a wave involves the transfer of energy and sound waves transfer energy through molecular vibrations of the medium through which it propagates. And the material properties determine how quickly vibrational energy can be transferred through that material.

A quick google search reveals simple formulas to compute the speed of sound in any medium and all those formulas are frequency independent. Since the speed of sound depends on material properties, it can also be considered as a material property.

An analogy here would be the speed of light in a vacuum. Irrespective of whatever the frequency of the source of light is, the light wave always propagates at $3 \times 10^8 \ \mathrm{m/s}$ .

Here's an explanation. The molecules of water are closer packed together (the material is denser than air). This allows faster momentum and energy transfer because they are closer to each other. Essentially, the denser the material, the faster the sound wave will travel through the material. The wave travels faster since the molecules are closer together than in air.