Sometimes in the taverns you'll spot other captains, or they will approach you when you enter.
If you talk to them (them not approaching you) talk about the business, and if he/she has something planned you'll be invited to their ship for a bit more detailed conversation. (It's basically the same when they approach you)
So, you go to port, get on the ship, and with "sail to" find their ship and sail to it. When close enough, launch a boat and meet them on board. He will tell you about some fleet carrying goods (silver/gold/slaves mostly) that was caught by storm, and ships were badly damaged, so the crew is waiting for a fleet to take them and their goods to safety. If you reject before he tells you the details, you can go freely and possibly deal with that captain in the future, but if you reject the deal after you hear the details, captain will hide and his crew will attack you (bare in mind that you're alone on that ship, so it's usually 5-6 (maybe more) people against you alone) and you won't be able to deal with him in the future if you survive.
Anyway, after agreeing to the deal you won't have much time to reach the destination so save prior to entering the map (in case you miss a location, storm, battles, etc etc). If you reach that shore on time you have to moor, and than fight begins - similar to city capture. After all sailors from that fleet are dead, pirate captain will approach you and tell you about your share which was loaded on your ship(s) - from what I've seen it's 50% of the loot, so it can be very very profitable, especially if you have only one ship, in that case only sailors form the pirates ship will attack the "enemy".
Don't know what happens if pirate captain dies, or if there are any other missions you can do with them...so if you have any info on this please contact me and I'll add it.
Based on original from Skodarap's CoAS Site (used with permission). Original is here .