Guide to finding gems on the auction house

All crafted socketable gems are named in a particular two-part pattern:

<Stat_prefix> <Gem_name>

Where

<Stat_prefix>: A name that defines what stats the gem have. All gems with that name share those attributes, though the values will vary.
<Gem Name>: The base material used to make the (socketable) gem. The better the base material, the greater the resulting attributes.

Generally:

Gems introduced with Mists of Pandaria have better stats than those from Cataclysm, Wrath of the Lich King or Burning Crusade
Gems with a rarer item quality (Epic, Rare) have better stats than those with lower quality.

To find the gem you want, you can search for the <Stat_prefix> part of the name, depending on what socket and stats you are looking for, then use the quality selector on the Auction House UI to specify what amount of the desired stats you want (and how much gold you are willing to spend). Alternately, you can choose in the subset of gem the color you want and specify the quality, then it will produce a longer list of gems you can choose from.

Patch 4.0.1 revised the gem system to be a little simpler. Several stats were removed along with existing stats being moved to a different color, causing the corresponding green, orange, or purple gem to either be removed, changed, or added. Biggest change was hit rating, intellect, and dodge rating moved to blue, red, and yellow (previously yellow, yellow, and red) respectively. Yellow stormjewels were removed and mastery rating will premiere on yellow gems for patch 4.0.3a.

Red Gems

[Blood Garnet] · [Living Ruby] · [Crimson Spinel]
Stormjewels · [Bloodstone] · [Scarlet Ruby] · [Cardinal Ruby]
[Carnelian] · [Inferno Ruby] · [Queen's Garnet]
[Pandarian Garnet] · [Primordial Ruby]

Name	Stat
Bold	Strength
Brilliant	Intellect
Delicate	Agility
Flashing	Parry Rating
Precise	Expertise Rating

Blue Gems

[Azure Moonstone] · [Star of Elune] · [Empyrean Sapphire]
Stormjewels · [Chalcedony] · [Sky Sapphire] · [Majestic Zircon]
[Zephyrite] · [Ocean Sapphire] · [Deepholm Iolite]
[Lapis Lazuli] · [River's Heart]

Name	Stat
Rigid	Hit Rating
Solid	Stamina
Sparkling	Spirit
Stormy	PvP Power

Yellow Gems

[Golden Draenite] · [Dawnstone] · [Lionseye]
[Sun Crystal] · [Autumn's Glow] · [King's Amber]
[Alicite] · [Amberjewel] · [Lightstone]
[Sunstone] · [Sun's Radiance]

Name	Stat
Fractured	Mastery Rating
Mystic	PvP Resilience
Quick	Haste Rating
Smooth	Critical Strike Rating
Subtle	Dodge Rating

Purple Gems

"Matches a Red or Blue Socket."

[Shadow Draenite] · [Nightseye] · [Shadowsong Amethyst]
[Shadow Crystal] · [Twilight Opal] · [Dreadstone]
[Nightstone] · [Demonseye] · [Shadow Spinel]
[Roguestone] · [Imperial Amethyst]

	Hit Rating	Stamina	Spirit	PvP Power
Strength	Etched	Sovereign	-	-
Intellect	Veiled	Timeless	Purified	Mysterious
Agility	Glinting	Shifting	-	-
Parry Rating	Retaliating	Defender's	-	-
Expertise Rating	Accurate	Guardian's	-	-

Green Gems

"Matches a Blue or Yellow Socket."

[Deep Peridot] · [Talasite] · [Seaspray Emerald]
[Dark Jade] · [Forest Emerald] · [Eye of Zul]
[Jasper] · [Dream Emerald] · [Elven Peridot]
[Alexandrite] · [Wild Jade]

	Hit Rating	Stamina	Spirit	PvP Power
Mastery Rating	Sensei's	Puissant	Zen	Infused
PvP Resilience	Balanced	Steady	Turbid	Vivid
Haste Rating	Lightning	Forceful	Energized	Shattered
Critical Strike Rating	Piercing	Jagged	Misty	Radiant
Dodge Rating	Nimble	Regal	-	-

Orange Gems

"Matches a Red or Yellow Socket."

[Flame Spessarite] · [Noble Topaz] · [Pyrestone]
[Huge Citrine] · [Monarch Topaz] · [Ametrine]
[Hessonite] · [Ember Topaz] · [Lava Coral]
[Tiger Opal] · [Vermilion Onyx]

	Strength	Intellect	Agility	Parry Rating	Expertise Rating
Mastery Rating	Skillful	Artful	Adept	Fine	Keen
PvP Resilience	Resplendent	Willful	Lucent	Splendid	Tenuous
Haste Rating	Fierce	Reckless	Deft	-	Wicked
Critical Strike Rating	Inscribed	Potent	Deadly	-	Crafty
Dodge Rating	Champion's	-	Polished	Stalwart	Resolute

Meta Gems

Main article: Meta gems

[Earthstorm Diamond] · [Skyfire Diamond]
[Earthsiege Diamond] · [Skyflare Diamond]
Starflare Diamond · Earthshatter Diamond (not crafted, can only be bought)
[Shadowspirit Diamond]
[Primal Diamond]

While meta gems also use the "<Stat_prefix> <Gem_name>" naming scheme, there are many effect combinations, making a table by attributes impractical. See Meta gems for a full listing.