I'm the Map, I'm the Map, I'm the Map, I'm the Map...
Maps are Path of Exile's answer to the repetitive grinding of a few endgame zones once common in ARPGs. Diablo players, for example, will remember running Mephisto, Chaos Sanctuary, or Baal approximately 474,312,281,384 times to level up and access the best endgame gear.
(Actually, I looked this up out of curiosity: it's approximately 6,000 Baal runs to hit Level 100 in Diablo II.)
While you can go back and re-run the zones from the story campaign, it's usually not a good idea to do so once you have access to Maps, which have much greater rewards and scale to higher levels.
Maps are consumable items found as drops from monsters in the world, similar to Currency items. They open portals to a fresh zone that you can clear for gear or experience. Each map has a specific tileset and tier. We'll talk about tiers in a moment.
Unlike regular story zones, however, Maps can have one or more Affixes applied to them. These affixes can do things like increase monster damage, apply curses to you, empower the bosses of the map, and so on. Each affix adds extra loot drops, but makes the map more difficult in exchange. Like any other item, maps can be modified by currency items - most commonly, you'll just use an Orb of Alchemy to turn it into a Rare map with many affixes.
Once you have a map, you can take it to the Templar Laboratory, located in the Epilogue, or more likely use it in the Hideout-placeable Map Device you'll gain access to shortly after reaching the Epilogue. Maps can also be brought to the various Masters to open maps that contain their special missions, provided that you have one of their missions available (the Atlas of Worlds, described later, displays how many of each Master's missions you have). When used, a map generates 6 portals to the zone it creates.
Entering a portal consumes it, meaning that if you die (and thus resurrect outside the map), portal out, disconnect, etc., you will consume another portal getting back in. Once the portals are all gone, the map is no longer accessible from the outside, potentially losing any loot that might be left in it, so play carefully! In parties, every member entering consumes a portal, so you'll get less of a margin for error in party play.
The tier of a map determines the level of the zone that it opens. Maps open zones with a level equal to 67 plus their tier, so a tier 1 map opens a 67+1 = level 68 zone, a tier 5 map opens a 67+5 = level 72 zone, and so on.
Normal monsters in each map will drop items with an item level equal to the zone level of the map. Magic monsters add 1 extra level and Rare monsters add 2, so the highest possible level of drops in a map (except for very specific circumstances) is 2 levels above its zone level. For example, a tier 1 map, which opens a level 68 zone, can drop items of item levels no greater than 70 under normal circumstances. Since certain items require high item levels to appear, this means that some valuable items can only appear in higher-tier maps.
Map tiers are grouped into three categories, indicated by the color of the map item's icon. White maps range from Tiers 1 to 5; yellow maps range from Tiers 6 to 10; and red maps range from Tiers 11 to 15. There are also special Tier 16 maps containing endgame bosses, and the final endgame fights take place in special Tier 17 maps. Higher-tier maps can roll more dangerous affixes, with the new affixes appearing at tiers 6 and 11.
The choice of exactly which map within a tier can drop in certain zones is subject to moderately complex mechanics. For the details on these, see the page on The Atlas of Worlds.