You can get this quest in any city. While walking the streets you will get approached (or you can go on and talk with each and every person on the street until you find the quest giver) by a male/female character asking you for help. They say that some pirate has kidnapped their husband or wife, and they will offer you some money for your assistance. The amount of money offered increases the longer you play.
They will tell you the name of the captain and the ship, and wait in the church until the task is completed. There's no time limit for this quest, and the ship will get stronger depending on your level. There are two ways to find this captain:
1) Traveling the world map and hoping you'll find him by chance. If you're lucky, you can meet him ashore on a colony and request he give you back the prisoner, but of course he'll refuse. In this case, go back to your ship and exit to the world map and you'll see his ship - a ship with red sails - near the colony. Attack him, board him, and you'll complete the quest just fine. Alternatively, you can also spot a ship with red sails on the world map, just sailing around. Approach this ship and engage, and then board her. In case it has a friendly flag and you don't want to ruin your own relationship with that nation, just wave the jolly roger flag and then board it. You'll still lose reputation, but not as much. After you kill the captain, the prisoner will approach you, so you'll have to wait a bit with looting the cabin.
2) Tracking him down with the help of the Port Controller. In this case, simply ask the port controller in each port about "captains that were in port recently". If you're lucky, he will tell you about this particular captain and his ship being in his port on [Date] and left on [Date]. Be sure to check the dates! Sometimes, especially if you've been tracking him for years, he will have come to the port twice, and so the port controller will give you the earlier date instead (for e.g. year 1666 when you're already in 1668). In this case, simply exit to the world map and moor again, asking him again and he will give you the latest date this time (if it still doesn't match up to your tracking, he might have entered the port three or more times; in this case, just repeat and you'll eventually get the latest date). The key here is to look out for how recent it is - if you're in October 1667 and he left port on September 1667, then chances are, his ship is somewhere near the port traveling in the direction of his destination port. However, if he left port in January 1667, then he's probably somewhere else by now, and you'll have to continue tracking him.
Once you've found him, make sure to board him. The mission will fail only if you sink the ship with prisoner on it.
BUG: Sometimes, after boarding him and winning the deck fight, you'll immediately enter the loot screen instead of the captain's cabin. There seems to be no way around this except reloading to an earlier save before you obtained the quest. Note that this bug can "spread" and affect other Captive Groom/Bride quests you currently have pending as well.
Based on original from Skodarap's CoAS Site (used with permission). Original is here .