Any magnetic compass absolutely will work underwater.
Several companies (e.g., PNI, OceanServer) build and sell electronic compass modules based on flux-gate technology specifically for underwater applications.
Buoyancy gliders and small AUVs or ROVs usually rely on flux gate compasses to sense heading because they are small, relatively inexpensive, and consume little power. Larger, more expensive vehicles often have a magnetic compass for backup, but use a gyrocompass (RLG or FOG) as the primary orientation sensor because it is more accurate than a magnetic compass and is not susceptible to local magnetic disturbances (like the vehicle's motors or batteries).
The accuracy of your compass is important because if you are trying to navigate by dead reckoning -- or by inertial navigation -- any errors in your orientation estimate make errors in your position estimate grow quickly. To improve the data rate and accuracy of a magnetic compass, and to make it less susceptible to local magnetic disturbances, you can combine angular rates from a gyro with the angles from a compass using a complementary filter or a Kalman filter. But trying to use only a gyro, you will run into trouble as you integrate to get angle -- over long periods, your integration will drift. That's why the complementary filter solution works -- the magnetic compass is a bit noisy, but stable over the long term, while the gyro is accurate and fast over the short term, but drifts unbounded in the long term.
As Ian mentioned, if you are trying to track your robot's position, you will also need a velocity estimate for dead reckoning. If you are in stationary body of water, like a pool, you can probably get away with "counting propeller turns", but you would need to calibrate your propeller. In the field, most vehicles will use a Doppler velocity log (DVL) to measure speed relative to the seafloor. That is an expensive sensor to add, but well worth it if your application requires precision navigation.
Refer to this article for a fairly recent survey on underwater navigation technology.