You need an Armory to build Artillery and a Shipyard for ships.
|Wagon Train||39 hammers|
|Artillery||192 hammers, 40 tools, Armory|
|Caravel||128 hammers, 40 tools, Shipyard|
|Merchantman||192 hammers, 80 tools, Shipyard|
|Galleon||320 hammers, 100 tools, Shipyard|
|Privateer||256 hammers, 120 tools, Shipyard|
|Frigate||512 hammers, 200 tools, Shipyard|
Costs in Europe:
|Artillery||500 gold + 100 gold for each Artillery you've bought|
Initially the cost of Artillery in Europe is much lower than that for ships, but it gradually rises. In the colonies Artillery is relatively expensive to build compared to ships.
I used to think that fortresses full of Artillery were the way to fight the Royal Navy, but I was thinking in terms of early European prices (Artillery for 500-1000 gold, Frigate for 5000 gold), and assumed that colony prices have similar (10:1 - 5:1) proportions. They happen not to, and a Frigate costs about as much as 3 units of Artillery (8:3 in term of hammers, 5:1 in terms of tools).
A Frigate attacking a Man o'War has a reasonable 50% chance of winning (16+50% attack bonus strength against plain 24) and is mobile, so it can protect a few colonies.
A lot of Artillery in a Fortress has higher firepower, doesn't get damaged in case of a defeat against ships and protects against land attacks as much as against naval attacks, but you need to build those Fortresses everywhere (or at least Forts), and you need a lot of Artillery in every coastal colony, because it's extremely immobile (only 3 squares per turn on roads, and it's very vulnerable in travel - use a Privateer or some other ship to transport them if you can).
Making Artillery is still probably a better idea than building Frigates, but not by as big margins as I once thought.
Building Galleons and Privateers is a good idea, unless all your Carpenters are too busy with their buildings (during development of industry you need so many buildings that you're very likely to have too few Carpenters).