If you conquer Ivernis (South Ireland) first, you can build ships there too.