I have been thinking about that a lot actually. I want that in my MMORPG and I'm hoping for some nice suggestions too. I have mobs that can walk on the ground, of course, and I also have ones that can walk on the water surface (like water elementals) but I have not yet added fish, sharks, sea creatures, etc, because I've not been able to come up with a solution I'm happy with yet.
All I've come up with so far is to set any triangles that are below a water plane to a different area and basically have the water mob navigate on the terrain below the water BUT keep track of an elevation between the terrain and the water surface. So, if a shark is attacking a player, for example, he navigates to the player's XZ on the ocean floor but the server will also have the shark rise or sink to the player's Y position as it moves. If it's random movement within the body of water, you could just pick a random target Y location. You don't have to worry about it crawling on islands because their triangles would be set to the normal ground area.
There are a couple issues with this approach, hence, why I haven't implemented it myself yet. This means that the ocean floor/lake floor/river floor can't be jagged or steep. Even though the mob is swimming above it, the floor actually has to be navigable. The other issue is a minor one. There is more complexity in handling vertical movement. Think about Y movement only or an XZ change that is small but a large Y difference causing the mob to rise or fall too quickly, unless you code to handle those situations.
Paul