jremington:
There has recently been a real breakthrough in underwater acoustic communications.Researchers as Newcastle University in the U.L, have developed spread spectrum nanomodems: very cheap ($70 instead of $7000), very low power, small and yet long range (km).
A better way to transmit messages underwater
I would hope that commercial versions of these might appear in the next couple of years.
There's a slide package describing the system at a high level here which in turn references a IEEE paper.
One of the interesting side benefits is that with multiple fixed reference nodes, the system can do platform navigation, though they don't quantify the accuracy.