[NTJedi]

You might need to explore the recruitable independents along the shore as a few places might provide special amphibian types for purchase... thus no need for magic.
This is usually the easiest and fastest way to move into the water provinces.

On a side note the Independent Land AIs are terrible about attacking water provinces which provides the human player a huge advantage. If playing against AIs you'll eventually stop playing with water provinces because the human player has such a strong advantage.