The Maze Map is useful mostly for finding your way around the various mazes in the Twilight Forest. Like the normal map, it can see through walls, but unlike the normal map, the Maze Map will show you a slice of the world at your current depth or altitude. It is also zoomed in enough to show even the thinnest walls.
The Maze Map can be crafted with a token known as a Maze Map Focus, surrounded by 8 blank paper. You'll have to find the focus yourself, though if you spend enough time in Labyrinths or Hollow Hills, you'll run across one eventually.
But if the Maze Map can see through walls, can it see through stone to reveal all the treasures within? Well, if you perform a little upgrade, it can. It's expensive, but will almost certainly pay for itself quickly.
Crafting the Maze Map with a block of diamond, a block of iron and a block of gold (shapeless recipe) will enable its ore-finding powers. It will search for ores within 3 blocks higher or lower than your current position and display them in a colorful manner.