Why do some types of waves disperse? We know that some mediums/waves are non-dispersive such as air for sound waves, and waves on a string. But, why do some waves, for example deep water waves, disperse?
I am trying to understand the underlying physics behind the reason that the velocity of a water wave depends on the wavenumber $k$.
 A: 
But, why do some waves, for example deep water waves, disperse?

Dispersion can arise from several things.  However, the basic fundamental idea is that the medium responds to the wave in some way (e.g., the wave excites a resonance in the media).
Example:  Plasmas and Electromagnetic Waves
In the case of a plasma, electromagnetic waves can locally polarize the media inducing small dipoles (or induce currents, depending on the mode and the media) that alter the propagation of the wave (e.g., reduce the phase speed).  If the medium is non-dispersive, this is equivalent to saying that the medium response time to the wave is so slow as to be zero compared to the frequency of the wave (i.e., it's like currents are induced instantaneously).  However, if the media has a finite response time, then the phase speed of the wave will depend upon its frequency.
Two Types of Dispsersion
There are two ways to think about dispersion, spatial and temporal.  In the following I will use the word current to generally describe particle motions but it can just as well represent electric currents.
In spatial dispersion (still within a plasma), the total electromagnetic field at any given point is determined by the currents within a volume centered on that point.  The larger the volume necessary to determine the field, the stronger the spatial dispersion.
In temporal dispersion (still within a plasma), the total electromagnetic field at any given point can depend upon currents from previous times.  The longer the memory of these previous currents, the stronger the temporal dispersion.
Both of these are representations of the concept of non-locality, i.e., the wave properties at any given spatial and temporal position may not be independent of other spatial and temporal positions.

I am trying to understand the underlying physics behind the reason that the velocity of a water wave depends on the wavenumber k.

In the case of water waves, the non-locality I mentioned early is introduced by the orbits of individual fluid elements (or wave orbits) as a wave passes.  The driving force is generally wind which generates non-homogenous pressure gradients over the surface of the water.  The restoring force is gravity (at short wavelengths, surface tension starts to matter and the waves are then called capillary waves).  The general dispersion relation for gravity waves is:
$$
\omega^{2} = g \ k \ \tanh{\left( k \ h \right)} \tag{1}
$$
where $\omega$ is the angular frequency, $g$ is the acceleration of gravity, $k$ is the wavenumber, and $h$ is the water depth.
In shallow water (i.e., when the water depth is less than the wavelength, $\lambda$), the wave orbits are compressed into ellipses and the wavelength no longer matters in the dispersion relation.  Then the phase speed reduces to (i.e., $\tanh{x} \rightarrow x$):
$$
\frac{\omega}{k} \equiv V_{ph} \approx \sqrt{g \ h} \tag{2}
$$
which has no frequency dispersion.
In the case of deep water waves (basically gravity waves), the orbits are not affected by the lake/sea/ocean floor and gravity acts as a restoring force during the fluid element orbits (or wave orbits).  Then the phase speed reduces to (i.e., $\tanh{x} \rightarrow 1$):
$$
\begin{align}
V_{ph} & \approx \sqrt{\frac{g}{k}} \tag{3a} \\
& = \sqrt{\frac{g \ \lambda}{2 \ \pi}} \tag{3b} \\
& = \frac{g}{\omega} \tag{3c}
\end{align}
$$
The basic idea for why the phase velocity depends upon the wavelength in a deep water wave is similar to that of a linear pendulum, since gravity is the restoring force in both cases.  One can imagine that the pendulum length is analogous to the wave's wavelength and you have a the equation for a simple harmonic oscillator.
A: I'm not sure whether you include math analysis in "understanding underlying physics", but the point is that the basic wave is the eigenvector solution of the operator considered in the physical system you study. 
For surface waves in fluids, writting imcompressible + irrotational + boundary condition at interface (i.e. Airy theory of waves  ) occurs to result in a non-linear relation between $w$ and $k$, so that c=w/k is not constant.
