This topic will have both parts of "The Story So Far" (when the second is released) that explains the chain of events that led to the Cataclysm storyline. All of it in detail is explained in "The Shattering". The last Warcraft novel that hit the market prior to Cataclysm as well as posts from players that notice stuff from questing in Azeroth and Kalimdor:
Official Blizzard Quote:
The Lich King's reign of terror was over. As if to affirm that a bright future would soon dawn on Azeroth, other joyful events occurred across the world. Archdruid Malfurion Stormrage was at last freed from his imprisonment by the shadowy Emerald Nightmare through the efforts of his love, High Priestess Tyrande Whisperwind, and her allies. Elsewhere, after years in exile, the highly intelligent gnomes and the fearless Darkspear trolls made gains toward reclaiming their respective homes in Gnomeregan and on the Echo Isles.
Yet just as hope was beginning to surge among Azeroth's races, tragedy struck. The world's elemental spirits grew increasingly erratic, setting off a series of deadly natural disasters. Agents of the nefarious Twilight's Hammer cult surfaced throughout Horde and Alliance cities, spreading word of the impending apocalypse. The world's leaders scrambled to find a solution to Azeroth's growing instability.
In the dwarven bastion of Ironforge, King Magni Bronzebeard undertook a mystic ritual to commune with the earth. The ceremony, however, had an unexpected effect: Magni was transformed into diamond and became fused to the depths of the mountain city itself. In the wake of his petrification, the Bronzebeard, Wildhammer, and Dark Iron clans agreed to rule over Ironforge via the Council of Three Hammers, but the city's future remained uncertain.
Meanwhile, Thrall journeyed to his ancestors' lands in Nagrand, hoping to glean insight from Outland's elemental spirits as well as other respected shaman. In his absence, Thrall appointed Garrosh Hellscream, son of the legendary orc Grom, as acting Horde warchief. Garrosh's brash demeanor inflamed relations between the Horde and the Alliance. A gruesome slaughter of druids in Ashenvale, which the Twilight's Hammer had perpetrated to look like an act of the Horde, escalated tensions further and sowed mistrust among Garrosh's own comrades.
In particular, Garrosh infuriated Cairne Bloodhoof, the wise tauren high chieftain. Believing that the new warchief would lead the Horde to ruin, Cairne challenged Garrosh to a duel of honor. Although the mighty tauren fought valiantly, no amount of strength could have led him to victory. The matriarch of the Grimtotem tauren tribe, Magatha, had poisoned Garrosh's blade, unbeknownst to either of the duel's combatants. Cairne became immobilized after he received a flesh wound during the battle, allowing the new warchief to land a killing blow.
Following the duel, Magatha's agents seized the tauren capital of Thunder Bluff for the Grimtotem. The usurpers also intended to murder Cairne's son, Baine, but the young tauren eluded his assassins and staged a counterattack. Ultimately, Baine and his forces reclaimed Thunder Bluff, expelling Magatha and her traitorous followers from tauren lands forever.
Unaware of these critical events, Thrall received an ominous warning in Nagrand from the Fury of Earth: the fear and turmoil of Azeroth's elementals echoed the condition of Outland just before that world—then known as Draenor—had been ripped apart. Yet Thrall had little time to act on this unsettling revelation....
In a sudden upheaval eclipsing the world's recent elemental unrest, Azeroth shattered. Violent quakes tore through the earth. Mountains of fire and magma burst from the ground. Colossal tidal waves obliterated coastlines and caused widespread flooding.
The Cataclysm had begun.
Now from personal experience i picked up a few things while leveling:
There's a little secret quest in Darkshore, in the Maw of the Void where you find a Demon Hunter - can't remember the name, but his title is "Herald of the Dark Embrace". This Demon Hunter was slain by Maiev while she was hunting Illidan and managed to return, even as a shadow of his former self (as in how powerful). This would indicate there is a way for Illidan to return aswell, since he's been far more powerful and has already escaped death by Arthas - should be harder than to avoid Maiev, Akama and 25 nerds
The Black Dragonflight:
As my gnome was questing in Badlands, i stumbled upon a very interesting quest chain. The task was to have a Black Dragon lay eggs (that we should steal), then create a certain device that would scan it for corruption and where the corruption originates and finally purify it. As it happened, the one that gave us the quest was a red dragon that intended to start a new "pure" black dragonflight, redeemed of all the corruption (that came from the Old Gods as the quest explained) and trick Deathwing to believe it was destroyed so that it would have time to hatch. Seems the end of the Cataclysm will bring forth some more... friendly Black Dragons!
The Queen of the Naga has returned. We even get to see her in at least one quest in Kalimdor (Darkshore again) and she's in league with the Old Gods. Apparently she made a pact with them to save herself and her Highborne from drowning and they were all transformed into the Naga. There's a bigger scheme including them in Hyjal but we won't find out before Cataclysm is released.
I'll be updating the post if i stumble upon other quality quest chains. Everyone else is also encouraged to post their thoughts on the new quests (or quests i failed to see - especially the Horde quests that i won't be seeing anytime soon) or simply comment on the way the story progresses!