Wasn't the Pandaren race some sort of joke originally? I thought it was April 1 or something when I heard about the new WoW expansion, but alas, no. I recall there being the Brewmaster in WC3, with what seemed at the time some half joking lore behind it.
Did the premise for this whole expansion just come out of nowhere or has it been building since then?
The Pandaren race has been around since Warcraft 3/Frozen Throne times when a monk named Chen Stormstout helped out Rexxar in an extra campaign (as you mentioned).
In regards to the April 1st joke, it was a joke back in the day. The information can be found here: http://www.wowwiki.com/Pandaren_Xpress
As far as the building aspect, there has been a lot of talk in the background about the race being added in going as far back as the announcement of the last expansion (Cataclysm). Most thought that it would have come in Cataclysm instead of the Goblin or Worgen, but that was not the case.
More info about the race can be found here without too much copy/pasting: http://www.wowwiki.com/Pandaren
The pandaren are originally from central Kalimdor where they established the Pandaren Empire. They were allies of the night elves until they saw their obsession with magic getting out of control. The clans severed ties and left Kalimdor behind eventually establishing a new home on an island they named Pandaria. After the Sundering, some pandaren returned to the "new" Kalimdor to explore it. "Where once the pandaren were a mighty empire, standing proud beside their night elf allies, now they are a simple people who want only peace and a safe home." Since the Third War, more pandaren have come to visit Kalimdor.
Hailing from their own secret empire, the pandaren are a race of humanoids resembling panda bears. This appearance leads some to underestimate these noble creatures, thinking them harmless and "cute". They may be cute, but they are not harmless. Pandaren have a long tradition of mystic warfare and are exceedingly strong and agile. The traditional pandaren fighting style focuses upon mobility, speed and precision, as well as stunning acrobatic tricks. Many pandaren are skilled at fighting bare-handed.
Actually, Pandarens started earlier then Warcraft 3, but that was the first game they made an actual appearance in game. One of the artists (I believe it is Samwise) loves pandas and drew pictures of them for his kids. Eventually he started working them into pictures for Warcraft/Starcraft and many old pictures from those games art have pictures of panda soldiers in them. Warcraft three evolved it a bit by introducing the Pandaren brewmaster into the game, which was modeled off of one of these pictures.
