Sometimes when you kill things in Outlands, you find motes in your bags.
Motes drop off of elementals. The type of elemental you're killing (shadow, water, fire, etc) has a decent chance to drop its type of mote.
Combine 10 motes to make one Primal.
Primal Shadow: Used for items and enchants that affect shadow damage.
What Drop Shadow Motes? Grind in Hellfire (60), Nagrand (65), or Netherstorm (69).
Primal Life: Most used for healer enchants and craftables, including Golden Spellthread.
What Drop Life Motes? Grind in Zangarmarsh* (64)
Primal Earth: Used for defensive enchants and armor (such as for tanks), most valuable when transmuted by an alchemist into Primal Fire.
What Drop Earth Motes? Profession grind by mining Fel Iron. Grind in Nagrand (65-70)*, Shadowmoon Valley (68), Netherstorm (68).
Primal Fire: The most sought-after primal, most loved by mages trying to tailor their +fire damage epic set. Used in +spell damage and fire-related enchants.
What Drop Fire Motes? Profession grind by mining Fel Iron. Grind in Blades Edge Mountains (68), Nagrand* (70), Hellfire Penninsula (70). Most of these can only be reached by flying.
Primal Water: Used in spellpower and frost-related enchants and armor.
What Drops Water Motes? Profession grind by fishing. Grind in Nagrand (65), Terrokar Forest (Skettis)* (70).
Primal Air: Most useful in agility-related enchants and armor.
What Drops Motes of Air? Grind in Nagrand (64-70) or Shadowmoon Valley*.
Primal Mana: Highly desired for caster epics and enchants, especially Mystic and Runic Spellthread.
What Drops Motes of Mana? Grind in Netherstorm (67), Isle of Quel'Danas (70).
Primal Might: Created by alchemists by combining one of each following primal: Earth, Air, Fire, Water, Mana. Used in heavy-duty epic craftables.
Primal Nether: Used in heavy-duty epic craftables. Attainable through running heroic instances, at a badge vendor, or off the AH.
* My favorite farming spot.
Nagrand is your best bet for most elementals: the elemental plateau is only reachable by flight, but has a plethora of fire, earth, and air elementals just for farming. (Fire is just hard to get if you can't fly.)
In south-central Nagrand: you find shadow elementals, and earth and air elementals are everywhere in Nagrand but a good spot is south of the shadow elementals so that you can keep grinding all three.
Water elementals are all over the lakes of Nagrand.
The only place for life motes is to grind the bog lords and their friends in Zangarmarsh, which actually gives you lots of Sporeggarr reputation (cute pet at exalted).
Motes of mana fall off of all kinds of things in Netherstorm and are now available from erratic sentries when you do your daily Quel'Danas quests. Sometimes if no one else is around, I kill extra sentries for the motes and average a primal every 3-5 days. Still, Netherstorm is less likely to run out of mobs to grind for motes, just watch out for mana drain abilities -- melee classes should be especially strong farming these motes.
Never vendor motes. Always give them to your guild bank, a friend who needs primals, or auction them. Never ever vendor. (I'm looking at you, Z. You vendored MANA! /glare)