[dirtywick]

Well, there's a few ways. Some commander units have an ability to sail, in fact there's a mercenary that can do it if you're lucky to find him available to hire. You can recruit amphibious units (right click on a unit to see it's stats, if there's a frog or fish thing there it can go underwater) from provinces you conquer, like Itchyids or Shamblers are somewhat common. There are also items you can forge, usually through water or air paths, that can let your commanders breathe underwater and even lead units underwater. There's also summons you can use, like Sea Dogs that can go underwater. From there, just conquer your way across the ocean.