Sailing

[Talleyrand]

You may have to research Thetis' Blessing in the Enchantment tree, but be careful because I've had entire armies drown after the pretender died and the enchantment broke.

[Recruit]

You can also forge water breathing items.

[Endoperez]

Sailing can move your forces quickly. Sailing commanders are great for raiding, great for taking those few island provinces, great for moving a force into enemy backyard, rampaging there for a while and then joining your main force in two turns, etc. In some maps, it can also be used for very fast movement of troops in your own land.

But it doens't get you underwater, that's true. To do that, you need:

1) units/troops capable of going underwater
2) item that lets a commander and/or units go underwater
3) Thetis' Blessing

It's easy to get items that let commanders go underwater, and you'll probably find at least one of: Shamblers, Ichtyids, Mermen in one of your provinces. Many undead can also go underwater, including all longdead and all soulless.
Air gives you Barrel of Air, Water gives you Sea King's Goblet and Nature/Water gives you Manual of Water Breathing. There are also lesser items that let you bring 10 or so units underwater.

[Ozymandias]

Sailing is actually an excellent mobility power, depending on the layout of the map. Try playing MA Vanheim on Urraparrand. If you want a commander who can lead all their troops into water, take a Lady of Fortune as your pretender. She has the special ability of leading armies under the sea.

[HoneyBadger]

If you're sailing, and you look around, and you're at the bottom of the ocean...that's not a good sign!