You need a Docks/Port. Whatever it's called.

You need tradable goods in the original province.

You probably need Merchants (and upgrades).

You also need ships in every portion of the sea that borders a province you wish to trade with.

Do you have ships out everywhere? It's expensive, and when you go to war, it's SO easy to be blockaded. But the payoffs, woof!