If water is incompressible, how can sound propagate underwater?

Water is compressible (nothing can be completely incompressible). Treating water as incompressible is just a (usually very good) approximation. Therefore, longitudinal waves are possible.

Wikipedia reports the bulk modulus to be about $2.2\ \mathrm{GPa}$. This puts the speed of sound in water at about $$v=\sqrt{\frac{\beta}{\rho}}=\sqrt{\frac{2.2\ \mathrm{GPa}}{1000\ \mathrm{kg/m^3}}}\approx1500\ \mathrm{m/s}$$

If for the purposes of your task you can treat water as uncompressible, then you can also assume that sound propagates instantly in it. Indeed there will be no sound waves in this case, the movement will be just propagated instantly from the source to the observer.

Since sound travels as longitudinal waves, sound waves should only be able to propagate in a medium through compressions and rarefactions. However, water, as a liquid, is generally treated as an incompressible fluid.

The underwater environment is characterized as an inhomogeneous medium, such inhomogeneity is due to point-to-point changes in underwater characteristics such as temperature, salinity, and pressure (depth), and other factors (see below). Such variation of sound speeds along the propagation path of acoustic signals causes refraction and often yields a continuous change in the gazing angle of a propagating signal.

Early experiments with water compressibility have been recorded almost 260 years ago, see: J. Canton, "Experiments to prove that water is not incompressible", journal_cover Philosophical Transactions of the Royal Society, 52 (1761) 640-643. (Archive.org).

Visit the London South Bank University webpage: "Explanation of the Density Anomalies of Water", section: "D13   Water has an unusually low compressibility (0.46 GPa$\underline{^{-1}}$, compare CCl4 1.05 GPa$\underline{^{-1}}$, at 25 °C) $\underline{^{[f]}}$", on their "Water Structure and Science" website for more than you could ever want to know about water:

[f] Others take a contrary view, stating that water's compressibility is twice that expected [53b]. This difference is down to the viewpoint and different theoretical expectations. In both cases, water's compressibility is unexpected; either being greater than expected due to water's open structure or less than expected (in spite of its open structure) due to the cohesive nature of its extensive hydrogen-bonding.
  [53 a-b] (a) H. E. Stanley, S. V. Budyrev, M. Canpolat, M. Meyer, O. Mishima, M. R. Sadr-Lahijany, A. Scala and F. W. Starr, The puzzling statistical physics of liquid water, Physica A 257 (1998) 213-232. (b) H. E. Stanley, P. Kumar, L. Xu, Z. Yan, M. G. Mazza, S. V. Buldyrev, S.-H. Chen and F. Mallamace, The puzzling unsolved mysteries of liquid water: Some recent progress, Physica A 386 (2007) 729-743.

"Although commonly erroneously thought to be incompressible, water has been understood to be compressible for over 250 years. It may be considered that water should have a high isothermal compressibility ($\beta_T$) and adiabatic compressibility ($\beta_S$), as the large cavities in liquid water allows plenty of scope for the water structure to collapse under pressure without water molecules approaching close enough to repel each other.

$\beta_T = - \left [ \frac {\partial V}{\partial P} \right ]_T \times \frac {1}{V} = \left [ \frac {\partial \rho}{\partial P} \right ]_T \times \frac {1}{\rho} = \left [ \frac {\partial L n \rho}{\partial L n P} \right ]_T = - \left [ \frac {\partial ^2 G}{\partial P^2} \right ]_T \times \frac {1}{V} = \frac {\left< \middle ( \delta V \middle)^2 \right>}{k_BTV} $

$\beta_S = - \left [ \frac {\partial V}{\partial P} \right ]_S \times \frac {1}{V} = - \left [ \frac {\partial ^2 H}{\partial P^2} \right ]_S \times \frac {1}{V}$

$\left ( \frac {\partial \alpha _P}{\partial P} \right )_T = - \left ( \frac {\partial \beta _T}{\partial T} \right )_P $

where $\beta_T, \beta_S, \alpha _P, k_B, P, T, N, \rho, V, H$ and $S$ are the isothermal compressibility, adiabatic compressibility, thermal expansion, Boltzmann constant, pressure, temperature, number of molecules, density, volume, enthalpy and entropy respectively; the ${\left< \, \, \right>}$ brackets indicate the fluctuations in the values about their mean values.

The compressibility at constant temperature ($\beta_T$) of water depends on fluctuations in its density. In 'normal' liquids, these fluctuations are expected to reduce with thermal motions as the liquid cools down. This is not the case for water below 46.5 °C (see below).

The deformation causes the growth in the radial distribution function peak at about 3.5 Å with increasing or pressure (and temperature), due to the collapsing structure. The low compressibility of water is due to water's high-density, again due to the cohesive nature of the extensive hydrogen-bonding. This reduces the free space (compared with other liquids) to a greater extent than the contained cavities increase it.

The speed and direction of sound in water and rock is far more complicated than the propagation of sound in ground level air. Propagation of sound is permitted by non-zero stiffness and lack of vacuum (a medium to transmit the sound). Even a steel rod will transfer sound.

As explained on the HyperPhysics website the speed of sound in gases, liquids, and solids is predictable from their density and elastic properties of the media (bulk modulus). In water it's 1482 m/s at 20°C.

Sound in liquids also travels as longitudinal waves, it is only in solids that traverse waves propagate. The manner in which sound propagates in liquids varies mostly due to depth, other minor factors are explained in detail below.

In shallow water reflections from the surface and bed play a role. When the sound source and receiver are located at the depth of the sound speed minimum, called the SOFAR or sound channel axis, some sound waves travel nearly straight, cycling above and below the axis, others almost reaching both the surface and bottom. At SOFAR depths sound waves traveling from the source at angles of less than about 12° are refracted back toward the sound speed minimum before ever reaching the surface or sea floor. Low frequency sounds are attenuated the least while high frequency sounds are most greatly attenuated in the SOFAR channel.

Sound traveling closest to the axis travels the shortest distance but at the slowest speed while sounds slightly off axis travel a curved path at a higher speed. This leads to explosions sounding like a series of bumps that get louder and louder as each path arrives at its destination.

In underwater acoustics, speed of sound depends on pressure (hence depth), temperature, suspended or dissolved contents, and salinity of seawater, thus leading to vertical speed gradients similar to those that exist in atmospheric acoustics. Sound may be absorbed by losses at the fluid boundaries. Near the surface of the sea losses can occur in a bubble layer or in ice, while at the bottom sound can penetrate into the sediment and be absorbed.

Sound speed
Approximate values for fresh water and seawater, respectively, at atmospheric pressure are 1450 and 1500 m/s for the sound speed, and 1000 and 1030 kg/m³ for the density. The speed of sound in water increases with increasing pressure, temperature and salinity. The maximum speed in pure water under atmospheric pressure is attained at about 74 °C; sound travels slower in hotter water after that point; the maximum increases with pressure. On-line calculators can be found at Technical Guides – Speed of Sound in Sea-Water and Technical Guides – Speed of Sound in Pure Water. Those webpages offer simplified and more complicated estimates of the speed of sound underwater.

Propagation of sound
Underwater acoustic propagation depends on many factors. The direction of sound propagation is determined by the sound speed gradients in the water. This is an important thing that happens in water, because the speed of sound travel in water with velocity regular. In the sea the vertical gradients are generally much larger than the horizontal ones. Combining this with a tendency towards increasing sound speed at increasing depth, due to the increasing pressure in the deep sea, causes a reversal of the sound speed gradient in the thermocline, creating an efficient waveguide at the depth, corresponding to the minimum sound speed. The sound speed profile may cause regions of low sound intensity called "Shadow Zones", and regions of high intensity called "Caustics". These may be found by ray tracing methods.

At equator and temperate latitudes in the ocean, the surface temperature is high enough to reverse the pressure effect, such that a sound speed minimum occurs at depth of a few hundred metres. The presence of this minimum creates a special channel known as Deep Sound Channel, previously known as the SOFAR (sound fixing and ranging) channel, permitting guided propagation of underwater sound for thousands of kilometres without interaction with the sea surface or the seabed. Another phenomenon in the deep sea is the formation of sound focusing areas, known as Convergence Zones. In this case sound is refracted downward from a near-surface source and then back up again. The horizontal distance from the source at which this occurs depends on the positive and negative sound speed gradients. A surface duct can also occur in both deep and moderately shallow water when there is upward refraction, for example due to cold surface temperatures. Propagation is by repeated sound bounces off the surface.

Wikipedia's webpage on the speed of sound, section: "High-precision measurements in air", lists the speed of sound in air as "... at 0 °C. The result was 331.45 ± 0.01 m/s for dry air at STP, for frequencies from 93 Hz to 1,500 Hz.".

Wikipedia lists the speed of sound in freshwater as "1481 m/s at 20 °C" but in seawater the calculations become more complex due to temperature and pressure resulting in a sound speed profile (SSP).

Here is an example SSP at a location north of Hawaii:

Propagation of sound in solids, such as rock, are subject to volumetric deformations (compression) and shear deformations (shearing) called pressure waves (longitudinal waves) and shear waves (transverse waves), respectively.

In earthquakes, the corresponding seismic waves are called P-waves (primary waves) and S-waves (secondary waves), respectively. The sound velocities of these two types of waves propagating in a homogeneous 3-dimensional solid are respectively given by

$$c_{\mathrm {solid,p} }={\sqrt {\frac {K+{\frac {4}{3}}G}{\rho }}}={\sqrt {\frac {E(1-\nu )}{\rho (1+\nu )(1-2\nu )}}},$$

$$c_{\mathrm {solid,s} }={\sqrt {\frac {G}{\rho }}},$$

where

$K$ is the bulk modulus of the elastic materials;
$G$ is the shear modulus of the elastic materials;
$E$ is the Young's modulus;
$ρ$ is the density;
$ν$ is Poisson's ratio.

The last quantity is not an independent one, as $E = 3K(1 − 2ν)$. Note that the speed of pressure waves depends both on the pressure and shear resistance properties of the material, while the speed of shear waves depends on the shear properties only.

Typically, pressure waves travel faster in materials than do shear waves, and in earthquakes this is the reason that the onset of an earthquake is often preceded by a quick upward-downward shock, before arrival of waves that produce a side-to-side motion.

Similar to seawater the propagation of sound within the Earth isn't a simple formula:

Typical speeds of sound are 330 m/s in air, 1450 m/s in water, but are about 5000 m/s in granite for p-waves; s-waves travel approximately 60% of the speed of their accompanying p-wave. S-waves can not travel through liquids, that includes the Earth's core.

Since compression is essential to sound propogation, how do phenomena such as whale calls and underwater speakers work?

Water is compressible. The propagation of sound is possible in gases, liquids and solids.