Recommended crafts? Lots of choices.
Main Production crafts:
For leather-wearers, try skinning and Leatherworking. You'll make armor for yourself. At later levels it can branch into Dragonscale, Tribal, and Elemental. Hunters and Shaman can make Mail for themselves post 40, and Druids and Rogues can keep making leather.
For Mail/Plate/Weapon users, you have Mining and Blacksmithing. Any meleer can benefit from the weapons, but Warriors and Paladins get benefits from making armor for themselves as well. Later on you can choose armorsmithing (for very nice plate recipes) or weaponsmithing, with a choice in which route you want to go. Very beneficial.
For Cloth-wearers, Tailoring makes their armor. Mages, Priests, and Warlocks can consider this. Unlike other crafts, tailoring doesn't need a gathering profession, as you use cloth that drops off humanoid mobs. However, skinning helps in making some bags, mining helps in some odd recipes that need gems, and Enchanting is good as I'll explain next. Oh, Tailors also make Bags, containers, so you can carry more items. Anyone can benefit from these.
Enchanting: The desire and despair of many. Enchanting can make you a lot of money late in the game, BUT like all good things, it comes with a price. And oooo boy, does enchanting have a price. You enchant items to add permanent stats to them (only one enchant per armor/weapon piece at a time). But you get materials by disenchanting (read: destroying) green+ quality armor. This can get very expensive later on, when a green item piece will run for 3-5 gold and only give you a couple of reagents. Enchanting works well with Tailoring (which allows you to make your own items to disenchant), or with a gathering skill for some money to buy items to disenchant. It also works as a gathering skill, by disenchanting items and selling them on the AH. Enchanting is not recommended on your first character, as you'll be hard-pressed to get enough materials to skill it up, and you'll be extremely poor.
Gathering skills: Mining, herbalism, and skinning. Good for making money, especially when you start out. Get materials and sell them for constant gold. It's not recommended to take mining and herbalism, as both track materials on your mini-map, but only one can be active at a time.
Consuming crafts:
Alchemy: This is a fun one. You make potions that (mostly) last for an hour, or until you die. You can make health and mana potions, +stat potions, +resistence potions, +effect potions (give your weapon an added frost or shadow bolt, that kinda thing), and other htings like invincibility, invisibility, and more. At later levels you can Transmute Arcanite, which will bring you constant money. You practically NEED herbalism for this, as all normal potions use herbs. ALchemy can be used by anyone, and anyone can use alchemy potions, even without alchemy skill; thus, you can sell your potions pretty well. I took alchemsy on my first character, and it worked out great. Alchemy's good for any class, but more closely associated (in my experience) with support and healing classes.
Engineering: The only craft I daresay cannot make money (not easily, at leats, and not a lot). However, it is arugably the most useful of them all. Engineering is a wonderful PvP craft. You make bombs and gadgets. Some have disorienting effects, others just do damage, etc. Mining goes very nicely with Engineering, as you need the ore and gems to make things. However, the problem with engineering (when it comes to profitability) is that only engineers can use most of the items created. So your potential customers can make everything you can sell (mostly). Engineering has two branches as well: Goblin and Gnomish. And yes, Horde can be Gnomish Engineers. Bombs are expensive, but incredibly useless; I would think that front-line meleers would get more out of it than healers and supporters, though. Although few would suspect a Priest to suddenly whip out a Gnomish Deathray and Crit for 2000+ damage... hmm...
So, that's the lowdown on all the skills, who uses them, and what gathering skills go with them. The secondary skills were already listed, but I'll go over them quickly:
Fishing: Grab a rod and fish! You can eat fish, and some are used in alchemy. Fishing is great to powerlevel cooking; I got to 300 cooking using only fish. There is a new fishing tournament coming out in the next patch, but I'm not sure what it'll be like and what the prizes are. Fish sell for very little to vendors; this isn't a big money-winning, but it can save you a lot if you're a Hunter who needs to feed a pet.
Cooking: Use those almost worthless drops off beasts to make better food. Food reduces downtime, and can add stats for a few minutes. Some of the food in the game has some nice stats, like +10 agility or mana regen. Also, cooked food makes pets happier; once again good for Hunters.
First Aid: In my opinion, a should-be mandatory skill for everyone. Everyone can use this skill. You take cloth from humanoids, and make it into bandages. Bandages act as channeled spells to restore hp over a short amount of time. The catch is, it gets interrupted if you are hit, and each time you start to bandages up, you get a cooldown of a minute before you can use another bandage. However, Heavy Runecloth Bandages give 2000 hp in 8 seconds. This is a wonderful time-saver for Warriors and Rogues, and a decent alternative to eating for them. It's a mana-saver for healers, and it saves even more mana if support gets hit but heal themselves. Another PvP necessity.
Okay, that's really everything ^_^ If you want to drop a primary trade skill, press k. On the page, select your tradeskill (actually click the little bar that shows how much progress you've made). There's a little X in the corner; press that to delete your tradeskill. Find a trainer to get another; if you need to find a trainer, ask a guard and they'll tell you.