The Map is a 5x6, 30 tile grid. Currently each Day's login gives players 10 new tiles to complete the map (this will probably decrease in the future). After all 30 tiles are revealed, the map is complete, and the player may travel to unlocked islands on the map. (Some islands may need to be finished to unlock others.)
The Map menu item is unlocked by building the Barracks.
The Map menu was introduced in the July 22nd 2010 update.