Well, you have to get the $15 upgrade (which includes the equivalent of the $20 storage upgrade as a bonus, so it's a good deal even without the new content).
The floating market that sells the new ships is located at about the location you get from drawing a line from Moonglow (at about where the south teleporters are) south, and from Magincia (about the bank level) east, and marking the intersection point.
After you get one of the new ships, then you have to get the cannons and ammo for them (which combined take about every crafting skill except Bowyer to make).
The Pirates themselves seem to primarily haunt the waters between Jhelom and Amoeba Island - and lately have been running in packs of ships.