Про открытия в Европе могу сказать неточно (совсем мало играл), но вроде было так. Иногда в зависимости от государственной политики получал "первооткрывателя", которого можно посылать в неизведанные части карты, что занимало больше времени, чем просто поплыть в известные места. Открыл некую землю, где никто из больших государств еще ничего не построил, можно делать колонию, посылая уже таки колонистов, которые еще должны были разобраться с местными аборигенами. После того, как колонистов стало достаточно, колония превращалась в полноценную провинцию.