You are right! It is a very hard and interesting problem. Radio will not work underwater. Inertial/mag sensors can be small and cheap but the quality is poor. Therefore I have been using some 'intelligent' (hate to use that word these days) processing of the data. It is still a relative position estimate if you can minimize the drift you are good to go. To help, we have communications between divers using acoustics. Using some cleaver DSP techniques and information sharing between divers you can do a lot.