I only found 3 pieces, not sure where the last one is. Bought the first one to start the treasure hunt, found the second one in a chest on a small island in the SE part of the overworld, and the third one was either a reward from an NPC or found in some chest, I forget. Anyone know where the last piece is?
Edit: Nvm, found it in the post ex-pirate tour area secret wall. Take the pieces to the Cartographer in the Great Library to get a new map, which will reveal a new dungeon on the overworld.