Common gems can be purchased from the following vendors for 2

•  Markus Scylan in Honor Hold
•  Reagan Mancuso in Thrallmar
•  Inessera on Aldor Rise, Shattrath City - checked, as at 28Jan2010, she does NOT sell gems, she sells designs.
•  Lisrythe Bloodwatch on Scryer's Tier, Shattrath City
•  Dealer Senzik in Stormspire

Color	Name	Effect
Red	[Bold Tourmaline]	+4 Strength
	[Bright Tourmaline]	+8 Attack Power
	[Delicate Tourmaline]	+4 Agility
	[Runed Tourmaline]	+5 Spell Damage
	[Teardrop Tourmaline]	+9 Healing
Yellow	[Brilliant Amber]	+4 Intellect
	[Gleaming Amber]	+4 Spell Critical
	[Rigid Amber]	+4 Hit Rating
	[Smooth Amber]	+4 Critical
	[Thick Amber]	+4 Defense
Blue	[Lustrous Zircon]	1 Mana every 5 seconds
	[Solid Zircon]	+6 Stamina
	[Sparkling Zircon]	+4 Spirit

Some uncommon gems can be purchased from  Dealer Senzik in very limited-supply, for 4 each.

Color	Name	Effect(s)
Red	[Bold Blood Garnet]	+6 Strength
	[Bright Blood Garnet]	+12 Attack Power
	[Delicate Blood Garnet]	+6 Agility
	[Runed Blood Garnet]	+7 Spell Damage
	[Teardrop Blood Garnet]	+13 Healing
Yellow	[Brilliant Golden Draenite]	+6 Intellect
	[Gleaming Golden Draenite]	+6 Spell Critical
	[Rigid Golden Draenite]	+6 Hit Rating
	[Smooth Golden Draenite]	+6 Critical
	[Thick Golden Draenite]	+6 Defense
Blue	[Lustrous Azure Moonstone]	2 Mana every 5 seconds
	[Solid Azure Moonstone]	+9 Stamina
	[Sparkling Azure Moonstone]	+6 Spirit
	[Stormy Azure Moonstone]	+8 Spell Penetration
Orange	[Glinting Flame Spessarite]	+3 Hit Rating	+3 Agility
	[Inscribed Flame Spessarite]	+3 Critical	+3 Strength
	[Luminous Flame Spessarite]	+7 Healing	+3 Intellect
	[Potent Flame Spessarite]	+3 Spell Critical	+4 Spell Damage
Green	[Dazzling Deep Peridot]	1 Mana every 5 seconds	+3 Intellect
	[Enduring Deep Peridot]	+3 Defense	+4 Stamina
	[Jagged Deep Peridot]	+3 Critical	+4 Stamina
	[Radiant Deep Peridot]	+3 Spell Critical	+4 Spell Penetration
Purple	[Glowing Shadow Draenite]	+4 Spell Damage	+4 Stamina
	[Royal Shadow Draenite]	+7 Healing	1 Mana every 5 seconds
	[Shifting Shadow Draenite]	+3 Agility	+4 Stamina
	[Sovereign Shadow Draenite]	+3 Strength	+4 Stamina

After phase 4 of the Shattered Sun Offensive, Shaani starts to sell all six types of Burning Crusade epic gems for 15 Badge of Justice each at the alchemy lab.