Gatherer

Here's a small guide on what patterns/items can improve your proffessions/skills. Please do feel free to comment if there's something wrong, or that I missed. If you like it, you may want to rate this comment ;-)

Using Blacksmithing
Riding+4% (requires 235) Enchant Plans: Mithril Spurs

Using Cooking
Fishing+10 (requires 100) Buff Recipe: Captain Rumsey's Lager

Using Enchanting
Fishing+2 (requires 145) Enchant Formula: Enchant Gloves - Fishing
Herbalism+2 (requires 145) Enchant Formula: Enchant Gloves - Herbalism
Herbalism+5 (requires 225) Enchant Enchant Gloves - Advanced Herbalism
Mining+2 (requires 145) Enchant Formula: Enchant Gloves - Mining
Mining+5 (requires 215) Enchant Formula: Enchant Gloves - Advanced Mining
Riding+2% (requires 250) Enchant Formula: Enchant Gloves - Riding Skill
Skinning+5 (requires 200) Enchant Formula: Enchant Gloves - Skinning
Herbalism+5, Mining+5, Skinning+5 (requires 375) Enchant Enchant Gloves - Gatherer

Using Engineering
Mining+5 (requires 205) Head Goblin Mining Helmet

Using Fishing
Fishing+15 (requires 50) 2-Hand Darkwood Fishing Pole
Fishing+20 (requires 100) 2-Hand Big Iron Fishing Pole

Using Leatherworking
Herbalism+5 (requires 135) Hands Pattern: Herbalist's Gloves
Lockpicking+5 (requires 120) Hands Dark Leather Gloves
Riding+10% (requires 350) Trinket Pattern: Riding Crop

From a quest
Fishing+3 (level 14, requires 10) 2-Hand Blump Family Fishing Pole
Fishing+3 (level 70, requires 70) Enchant Spun Truesilver Fishing Line
Fishing+5 (level 1, requires 1) Head Lucky Fishing Hat
Fishing+5 (level 1, requires 1) Feet Nat Pangle's Extreme Anglin' Boots
Fishing+5 (level 1, requires 1) Enchant High Test Eternium Fishing Line
Fishing+5 (level 70, requires 70) Head Weather-Beaten Fishing hat
Fishing+20 (level 64, requires 62) 2-Hand Seth's Graphite Fishing Pole
Fishing+25 (level 50, requires 44) 2-Hand Nat Pangle's Extreme Angler FC-5000
Fishing+35 (level 62, requires 62) 2-Hand Arcanite Fishing Pole
Riding+3% (level 50, requires 40) Trinket Carrot on a Stick

From reputation grinding
Riding+10% (level 70, requires 70 & honored with Netherwing) Trinket Skybreaker Whip
Fishing+30 (level 70, requires 70 & exalted with Kalu'ak) 2-Hand Mastercraft Kalu'ak Fishing Pole (Also allows underwater breathing)

From a vendor
Fishing+5 (requires 10) 2-Hand Strong Fishing Pole

OR! Maybe it's called GATHERER because it HELPS YOU with GATHERING PROFESSIONS? SHOCK&HORROR.

As of 5.0.4, this enchant does not stack with the +10 from the Mining pick/skinning knife. :(