To pull another mechanic out of Europe Univeralis IV in that at the start you can't explore or colonize empty provinces. In order to explore you first need to unlock the second idea in the exploration idea group. This idea lets you hire explorers to command your fleets or armies. Only forces led by an explorer can travel into uncharted territory. It doesn't matter if you have a thriving province adjacent to an uncharted province you can't go there or speak to the country that owns it until its been explored. Over time areas explored by other nations will be revealed to you but it a slow process.
Colonization on the other hand requires colonists which are a special resource? Depending on the ideas you've unlocked and the country you are playing you can have at most 4 colonists. Colonists are sent to empty provinces and setup a colony which slowly attracts settlers and over the course of a few years builds it up a city. Provided it doesn't get destroyed by natives or other players.
You could have something similar maybe instead of colonists its survey teams or science vessels. You need them to get colonies started or make a region safe for your ships to travel. It all depends on how you want to go with your game. Europe Univerallis IV is all about limiting what the player can do any one time, MOO was all about getting the player to expand as fast as possible.