It is not completely random. Each treasure map has 1-5 possible locations for the treasure to show up. There are five locations in total, which are:
- Donut Island
- Limestone Shelf Island
- Mordo Island
- Mountain Mass Island - Beach
- Mountain Mass Island - Mountains
For example, the Flowing Orb, given by the Treasure Map #4 can be found on Donut Island, Limestone Shelf Island or Mountain Mass Island on the beach. But it will never ever appear on Mordo Island or within the mountains of Mountain Mass Island. The Rage Orb, given by Treasure Map #1, on the other hand will always be on Donut Island.
The specific location is random as well. Most certainly there is a pool of possible locations. But I do not know how they are distrubuted among the maps.