The frequency of a sound wave cannot change as it crosses the water-air boundary. The wavelength can, and does, change but the frequency cannot because if it did there would be no way to match the two waves at the interface. This means that the higher frequency is not some quirk of the sound propagation, but that the colliding stones emit a higher frequency when in water.
To see why this is we need to consider how the sound is generated. When the two stones collide this generates a shock wave that propagates into the interior of the stones and makes them vibrate. At the surface of the stones the vibrations propagate into the surrounding medium as a sound wave, and that's ultimately what we hear. A stone will have some set of normal modes, and the shock wave will transfer energy into these normal modes exciting them in some probably rather random way that will depend on the details of the impact. The sound we hear is the combination of the frequencies and amplitudes of all these normal modes.
The reason that the sound of the impact is different in water is simply that the normal modes of an object in a medium like water are different to the normal modes of the same object in air. This is because water has a (much!) high bulk modulus than air and the surrounding water resists being moved by the surface of the vibrating stone far more than air does. It would be a brave physicist who would predict exactly how the sound would change because this will be complicated. Vibrational modes that cause lateral displacement of the water will tend to be slowed because the water has a higher density than air. On the other hand vibrational modes that cause compression of the water will shift to a higher frequency because water has a higher bulk modulus than air.
It might be possible to calculate exactly how the bulk modulus and density of the medium affect the normal modes for some idealised object like a perfectly elastic sphere. I've Googled for such calculations but with no luck - if anyone finds a relevant link please feel free to edit it in or add it as a comment. For now all i can say is that experiment shows the normal modes that shift to higher frequency dominate the sound we hear.
To expand on Xcheckr's answer:
The full equation for a single-frequency traveling wave is
$$f(x,t) = A \sin(2\pi ft - \frac{2\pi}{\lambda}x).$$
where $f$ is the frequency, $t$ is time, $\lambda$ is the wavelength, $A$ is the amplitude, and $x$ is position. This is often written as
$$f(x,t) = A \sin(\omega t - kx)$$
with $\omega = 2\pi f$ and $k = \frac{2\pi}{\lambda}$. If you look at a single point in space (hold $x$ constant), you see that the signal oscillates up and down in time. If you freeze time, (hold $t$ constant), you see the signal oscillates up and down as you move along it in space. If you pick a point on the wave and follow it as time goes forward (hold $f$ constant and let $t$ increase), you have to move in the positive $x$ direction to keep up with the point on the wave.
This only describes a wave of a single frequency. In general, anything of the form
$$f(x,t) = w(\omega t - kx),$$
where $w$ is any function, describes a traveling wave.
Sinusoids turn up very often because the vibrating sources of the disturbances that give rise to sound waves are often well-described by
$$\frac{\partial^2 s}{\partial t^2} = -a^2 s.$$
In this case, $s$ is the distance from some equilibrium position and $a$ is some constant. This describes the motion of a mass on a spring, which is a good model for guitar strings, speaker cones, drum membranes, saxophone reeds, vocal cords, and on and on. The general solution to that equation is
$$s(t) = A\cos(a t) + B\sin(a t).$$
In this equation, one can see that $a$ is the frequency $\omega$ in the traveling wave equations by setting $x$ to a constant value (since the source isn't moving (unless you want to consider Doppler effects)).
For objects more complicated than a mass on a spring, there are multiple $a$ values, so that object can vibrate at multiple frequencies at the same time (think harmonics on a guitar). Figuring out the contributions of each of these frequencies is the purpose of a Fourier transform.
Best Answer
Quite remarkably, one can amplify sound using the mechanical energy of a water jet, which was invented by a cousin of Alexander G. Bell, according to the book "Soap bubbles" by C.V. Boys available online, http://www.gutenberg.org/files/33370/33370-h/33370-h.htm, see pp. 113-115.