[NTJedi]

Usually the fastest way to enter water provinces early in the game is buying mercenaries which can enter the water. Once you've conquered one water province it's easier to expand into the others.

If the Mercs are not available for purchase then it depends on your gem income.