Similar to Captive Groom / Bride , you get this quest from random citizen when walking the streets of colony. (S)he tells you about a person that he came to new world with, but their ways parted at certain point. Anyway, everything is more or less the same as in Captive Groom / Bride quest, so please read that one for detailed instructions, I'll only point out differences here.
Ship you're looking for has green sails on world map - you shouldn't sink/board her (well, maybe you can board that ship, and pray captain surrenders, because if you kill captain mission fails).
When you find it, enter sea mode, get close to that ship and launch a boat. When on board talk to the captain. He'll tell you to give message to the person that gave you the quest. (problem might occur if this captain is flying under the enemy flag, but I think if you sail out of the battle distance (more than 850 away) you can change your flag to friendly one - if you have it ofc, if you don't just sail away and hope for the better luck next time you encounter it - though I haven't tried this method).
Return to the city you got the quest at, go to the church, talk to the person. He gives you reward and the mission is over.
Based on original from Skodarap's CoAS Site (used with permission). Original is here .