The Curse of Flesh is a curse suffered by some of the descendents of Azeroth's seed races, notably the dwarves and gnomes. The curse changed the structure and appearance of these races from their original stony/metallic forms into the fleshy forms we know of today.
The Curse of Flesh is revealed to have been created by the Old Gods early in Azeroth's history to "facilitate assimilation". The titans attempted to remove the curse (and the Old Gods), but found that the Old God infestation had grown too severe to remove without completely destroying Azeroth. Instead they bound the Old Gods within Azeroth.
Direct mentions of the Curse of Flesh
In the quest , a dialogue with Fizzcrank Fullthrottle details the removal of the curse from several gnomes by Gearmaster Mechazod which transformed the gnomes into "mechanical beings". The dialogue mentions that all creations of the titans eventually fell victim to it.
Sjonnir the Ironshaper
Sjonnir The Ironshaper mentions the curse when engaged.
Indirect mentions of the Curse of Flesh
While the Lorekeeper's Knowledge in Uldaman doesn't mention the Curse of Flesh by name, it clearly refers to the same events that are later described by the Tribunal of Ages. Interestingly, this dialogue was written during the original World of Warcraft, indicating that either this plotline has been planned for many years or has been built out of existing lore.
Jotun's title suggests that he is cursed, or bears a curse to others (which could be believed to be the Curse of Flesh).
In Archavon's Log (before Patch 3.3.0), for the Day 1051213, Archavon wrote "Archavon wake up, notice face feel soft. Not important. Go back to sleep." This could hint that he was, more or less, affected by the Curse of Flesh.
While General Bjarngrim in the Halls of Lightning does not directly utter the name of the curse, he does refer to it during the fight. His quotes imply that he compares himself with the player. Apparently, he also considers killing lifeforms affected by the curse to be the the solution of removing it.
In Icecrown Citadel, some of her dialogue states that the Curse of Flesh is a joke played by the Creators on their own creations. She also states that the sooner the cultists come to terms with the 'fact' that the Curse is a defect, the sooner they will come into a position to transcend it.
The Tribunal of Ages dialogue reveals that it was the curse that caused the transformation from stony earthen to fleshy dwarves while they were asleep in Uldaman. In the Warcraft Novel The Sundering by Richard A. Knaak, the altered timelime of The War of the Ancients descibes the dwarves as earthen. "His rough-hewn skin appeared to be a gray granite, his squinting eyes glittering diamonds. The beard was actually an intricate series of mineral growths that even made it looks as if the figure was graying with age." This suggests that the Curse of Flesh took place over a longer period of time and was still occuring upto at least 10,000 years ago.
The troggs too, were initially stone creatures. Like the Earthen, some were affected by the curse, turning them into fleshy troggs.
If Gearmaster Mechazod is to be believed, prior to the curse, gnomes appeared as mechagnomes. Unaffected mechagnomes have been found in the Storm Peaks, maintaining the mechanical systems of the Titans. There is a quest chain located north of the Borean Tundra in Northrend about the curse.
Sjonnir the Ironshaper appears as a vrykul with metallic skin. As such, it was thought possible by some players that the vrykul also had an original, more stony, appearance and also suffered from the curse. However, the 'iron' races were constructed by Loken, after and separately from all other titan creations. Instead, based on the quests  and  , it was discovered that the birthing of humans was originally a severe side-effect of the curse on the vrykul.
Aesir, the storm giants
The tol'vir of Uldum are a race of stone cat-centaur introduced in Cataclysm. The curse of flesh causes them to turn into the fleshy, wingless Ramkahen. The process can be reverted by powerful beings such as Siamat, and is some kind of a 'reward' for swearing allegiance to Deathwing.