From StrategyWiki, the free strategy guide and walkthrough wiki

Sea battles are really bad for you if you don't have a Letter of Marque. These letters let you hunt down ships of one nation. After you have got the letter for that nation, you need to stock up. Get a few good ships, fully equip them with cannons, crew, cannonballs and swords then go to the ship list and mark your convoy as a warship. If your ships are fairly low-powered then you will probably want to start by attacking traders for ships and goods,you might as well get all ships because even if they are rubbish, you can sell them for quite a bit of gold.

[edit] Attacking Traders

Traders have no background to their flags, to beat them just attack and board ships, take all the ships you can and all the goods, continue attacking unitl the entire convoy is in your command then go to a town under your command then sell all the bad ships and repair and re-equip the good ones (you may want to take them out of your convoy to repair them to save time)

[edit] Attacking Military Ships

Choose out a military ship (red background to flag) and follow it, when it's had a few battles, approach it and see how many sailors it has, if it's low (120-0) then attack it and capture the ships.