Like the first DeathSpank, the best way to get around the map in the game is through the use of magical Outhouses. To 'discover' an Outhouse, go near the general area of the Outhouse and you'll see that it's been activated. Outhouses are large brown buildings that are mostly found on the side of roads and usually right before a difficult part of an area. They're not hard to spot and you can easily see them in the area maps. Don't be mistaken about the Outhouses inside any caves or in the POW Camp. Since they're Out-Of-Order, they don't count for this achievement. All Outhouses that you need for the achievement are out in the open world and some you will need the pirate ship to gain access, since a few of them are located on islands.
A Map of all locations: Link
One location is NOT on that map, but don't fret. You'll be given a mini-transporter when you finish all the thongolith quests and talk with the thongolith researcher. Using the mini-transporter will transport you to the final Outhouse.