A comparative map showing the relative locations of Westeros and Essos, separated by the Narrow Sea.
For the uninitiated, the action of the Song of Ice and Fire novels (and by extension the TV series) takes place on two continents. The bulk of the action takes place on Westeros, a 3,000-mile-long landmass stretching from north to south, whilst the storyline of Daenerys Targaryen (and later other characters) takes place on Essos, a vast, Eurasia-sized landmass located just to the east of Westeros across the Narrow Sea. Oddly, despite the presence of extremely detailed maps of Westeros in the first four novels, the only map of Essos that has appeared is the area of Slaver's Bay, which was published in A Storm of Swords. Whilst useful, it didn't illuminate the rest of the landmass: the Free Cities, the Dothraki Sea, the Red Waste and Qarth, all of which Dany visited in her earlier travels.
HBO decided they wanted to use maps in the series to illuminate the action, including that of Dany and her journeys in the east, so George R.R. Martin provided them with some additional maps. The TV series will use these in the opening title sequence (which changes every episode to reflect the locations visited). In fact, as well as the map of the Free Cities it sounds like Vaes Dothrak and the Dothraki Sea will also be featured, and therefore presumably Lhazar (a region south-east of the Dothraki Sea, near Slaver's Bay, where Dany's storyline in the first novel and season climaxes).
Detailed map of the Free Cities region. Note that Norvos, Qohor and Volantis are located just off the eastern edges of the map. The location of Lorath is not known.
This is the first canon map of the Free Cities that has ever appeared, despite a significant amount of action in both the first and fourth books taking place there. Apparently a more detailed version of the Free Cities will also appear in A Dance with Dragons (incorporating some locations off the edges of this map).
Some locations of note:
Braavos: the northern-most of the Free Cities, a major location in A Feast for Crows and A Dance with Dragons.
Pentos: home of Magister Illyrio, site of Daenerys and Drogo's wedding in A Game of Thrones.
Flatlands: vast farming lands and estates beyond Pentos' walls. A relatively fertile land, but sometimes raided by the Dothraki when they are not appeased by being bought off.
Myr, Tyrosh & Lys: Three of the southern Free Cities, often clashing over the Disputed Lands.
Disputed Lands: an area of territory disputed between Myr and Lys (and sometimes Tyrosh and Volantis). A near-permanent warzone, bordered by the immense River Rhoyne to the east.
Stepstones: a chain of islands off Essos's south-western coast, the eastern-most end of the shattered land bridge that once linked Dorne and Essos.
Not on the map:
Ibben: a large island in the Shivering Sea north-east of Braavos, about a thousand miles east of Skagos. They have some colony states on the north coast of Essos (presumably east of Braavos on this map).
Norvos: an inland Free City due east of Pentos on a river. It looks like a map curves around the edge of the map east of Pentos, so Norvos is probably just off the map there.
Qohor: an inland Free City due east of Norvos, in the midst of the Forest of Qohor.
Forest of Qohor: a vast forest on the western edge of the Dothraki Sea.
Hills of Andalos: a low-lying hill range south-east of Pentos. The ancestral homeland of the Andals, who evacuated the area to invade Westeros after being visited by a vision from the Seven.
The Rhoyne: a huge, substantial river of Essos, forming the eastern edge of the Disputed Lands. Homeland of the Rhoynar, who fled to Dorne a thousand years ago. The southern Dothraki Sea lies east of the Rhoyne.
Volantis: a Free City, located at the mouth of the River Rhoyne. A location in A Dance with Dragons. A waystop for people travelling to Slaver's Bay, which lies many hundreds or thousands of miles to the south-east.
Lorath: the least-known and most enigmatic of the Free Cities, an island city. Its location is unknown. It's either extremely remote and little-known in Westeros, or it's a bit rubbish and no-one likes hanging out there.
Interesting to see if the map in ADWD features some of these missing locations :-)