Cataclysm starting sets
The Cataclysm starting sets are item level 232 uncommon armor sets. A distinct prefix is used for each class, although it actually refers to as many distinct sets as there are specializations for that class.
Ebonsoul
Wildsoul
Beastsoul
Magesoul
Monastic
Zealous
Seraphic
Shadowstalking
Stormbinder
Dreadsoul
Valiant
They are sold by:
Iris Moondreamer <Quartermaster> in Mount Hyjal
Erunak Stonespeaker <The Earthen Ring> in Vashj'ir
History
Before Patch 5.3.0, these sets were only available for characters instantly boosted to level 80 through the Scroll of Resurrection program. Upon logging in, such a character would be equipped in a full set of class and spec-appropriate gear in all slots. The Monastic set was not available at that point, as monks did not qualify for the Scroll of Resurrection boost.
In Patch 5.3.0, these items were added for sale to vendors in Mount Hyjal and Vashj'ir to enable fresh level 80 characters to more easily qualify for Cataclysm dungeons.
Patch changes
Patch 5.3.0 (2013-05-21): Now available from vendors. 
Patch 4.3.3 (2012-02-28): Added.