the Explorer is a title awarded for completing World Explorer, where you must completely explore all of the world maps for all continents in the game (Eastern Kingdoms, Kalimdor, Outland, and Northrend).
The title comes after the player's name, in the following format:
<name> the Explorer
In addition to the title, players will receive the [Tabard of the Explorer] in the mail upon completing the exploration of Northrend.
The achievement is possible without Cold Weather Flying, however it's more difficult. Check other online networks for closer information on how to get to Storm Peaks and other elevated areas. There is a character of level 1 who earned the title. (Check youtube.com)
The tabard is actually awarded on completion of the exploration of Northrend and is independent of the World Explorer achievement.