Around the Officer that gave you the Quest, stay a short while hanging there and you will notice other NPCs around him talking about in-game cohordinates of where Pirates have been noticed.
Write them down and purchase a Sextant from a Tinker. Then when on the Ship use the Sextant to get to the cohordinates mentioned and when you are in that area, say "Start tracking" to your Tillerman.
At that point, you will notice Arrows pointing directions. Follow one of those Arrows until you find the Ship it points to.
Some Ships will be of players, some will be NPCs Merchants, but some will be Pirates....
Hope it helps, have fun !!