AkuraTDB: First you need a Stable to build an Artillery Depot, which will initially allow you to build Yachts and Galleys. There's two researches at the Academy for new ships, "Develop new methods of woodworking" gives you Frigates(should be located under the tech that doubles your fishing boats capacity) and "Design rib system" gives you Battleships(tech is under the upgrade for ships' speed on the right of the list).

I also *heavily* recommend the "Train carpenters" tech that cuts the build times for ships down to a tenth of what it normally is.

I also recommend using Frigates in this mission over Battleships, as Battleships have a ridiculous gold upkeep.