Sail along the coast until you see one of the landmarks on the shore (those named stones that you can see along the coast here and there). The treasures etc. are always located close to those landmarks, even if you cannot see them in the treasure map (because they are too much inland from the shore).
If you can walk through normal landmarks when you are on shore (cabins, dead tress, temples) then you are in the wrong place. If you cannot walk through them, then the treasure is pretty close...