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.