Los barcos NO tienen su propia armada. Para transportar a un ejército en barco, pon el barco en el mar adyacente al puerto (no en el puerto), lleva hasta el mar al ejército y espera a que llegue antes de mover la flota (si no, te dejará el ejército en tierra.
Para colonizar primero tienes que descubrir la provincia que hasta entonces estaba en blanco (terra incognita)con una armada liderada por un explorador, o por tierra con un ejército liderado por un conquistador. Luego envias a un colono que tendrá un determinado porcentaje de posibilidades de fundar un asentamiento. Si lo consigue, ese asentamiento puede llegar a ser una provincia enviando más colonos. Cada colono que envíes (y tenga éxito) aumenta en 100 la población del asentamiento, cuando llegue a 1000, será una provincia.
Más o menos es así, no lo tengo absolutamente comprobado.
En lo de construir estás en lo cierto.
un saludo.