Most of the time when asking for a suggestion for a profession to pick people will say you're better off taking 2 gathering professions and just using the gold from resource sales to buy what you need.
There's a couple of problems with this concept however.
1. Supply and demand
2. (Gold) Efficiency
3. Long-term goals
Supply and demand
The question of supply and demand is fairly simple. If you want item X then you need to get it from somewhere. More often than not the item isn't available on the AH and if you're guildless (like me) then you're stuck spamming trade hoping to find someone who can make the item for a more or less reasonable price.
In that case you would've been better off having picked a profession and trained it whilst levelling.
In a lot of cases if you do pick a profession at the beginning of your carreer and keep it up it will always be slightly ahead of your level and you will have a few nice items waiting for you as you progress. This takes away the need to look for your needed items (at least for your chosen profession), saves time, headaches and results in a more efficient method of gearing your characters.
Having the profession also means that if you put in some time in gathering the materials for your desired item your item essentially becomes 'free'. Sure, you spent time gathering the stuff, but if you picked your profession early enough you can usually get the materials during the process of questing and gaining XP so you didn't really lose the time invested.
In the long term most people want to have all professions anyway. If you start with a profession once you are in the high 60s like a lot of people do you'll be throwing away whatever time you put into one of your 2 gathering professions and you usually spend a decent amount of time gathering materials in zones that don't give you any XP or quest progress.
Not only that but you'll be crafting items that would've been nice to have an X amount of levels ago.
Sure your epic mount will make a difference in how fast you can train things, and the gold you have to burn can help tremendously but only if the prices on the AH are reasonable or you have some other way to get the materials.
This leaves us a couple of ways to deal with professions efficiently. One is to still pick 2 gathering professions but simply not sell any of the materials gathered.
This requires a tremendous amount of bank space but will make it possible to level up a profession of your choice quickly at higher levels.
The other way is to simply pick a gathering profession and a crafting profession when starting your character and using the gathering profession to fuel your crafting profession.
What profession to pick is largely a matter of personal choice but there are professions that are more suited for certain classes.
For now let's take a loot at professions in general and then follow it up later with a more 'per class' approach.
Tailoring is a definite boon to any cloth wearing class. The ability to make some of the best 'green' cloth armor available especially if you have an incling towards shadow damage coupled with the capacity to supply yourself and all of your alts with bags means that tailoring has tremendous utility.
Tailoring however is _NOT_ a money making profession unless you happen to have specific popular patterns.
Since tailoring isn't dependant on a gathering profession (cloth drops off of humanoid mobs) it can be combined quite well with enchanting so that green items made during the levelling process of tailoring can be disenchanted.
While some tailoring patterns require gemstones, herbs or leather there is no real need to pick a gathering profession to go with tailoring unless you need the money from resource sales.
Leatherworking much like tailoring can be a boon to leather wearing classes but provides very little additional utility until later in the game where specific patterns like the riding crop become available. Feral druids will find leatherworking enjoyable from the perspective that it can cover some of their various equipment needs which can range from tanking gear to dps gear.
It is once again worth noting that Leatherworking is not suitable to make money with unless you are a skinning maniac and have an ample surplus of leather.
The obvious choice is to couple leatherworking with skinning so that you have a constant supply of resources. To a lesser extend enchanting which can be used to disenchant greens created during crafting.
Blacksmithing is a decent profession to take for the 'tanking' classes like paladins and warriors. It is often said that there are too few good patterns in the blacksmithing tree but for levelling purposes you will find that you can always use some of the armor components that you can craft. Weapons before weaponcrafting are often dependant on what recipes you can find on the AH. More often than not you can find cheap recipes on the AH for weapons but before level 30 you end up buying most of your weapons from the AH.
Blacksmithing does not make it possible for you to craft shields. I was sorely dissapointed by this since a good tank needs a good shield and not being able to make one reduces the utility of blacksmithing somewhat.
Pick this if you want to be able to make yourself some armor but be aware that there is never a shortage of decent 'metal' armor on the AH.
Blacksmithing is best combined with mining. It's obvious and it's far from realistic to depend on the AH for the resources you need to level this since it requires tonnes of various ores and stones.
If you pick blacksmithing be prepared to pick mining and also know that the utility of blacksmithing is limited except for the occasional piece of armor (and of course rare recipes later on).
Jewelcrafting is one of those skills that has a decent amount of utility in the early levelling phases since decent jewelry is rarely dropped or offered as quest reward. However jewelcrafting doesn't really come into it's own till near the end-game (60+) when you get socketed items in which you can slot various cuts of gemstones.
With a few good recipes you can make good gold with jewelcrafting but you will hardly be able to make decent returns with it until very late in the game.
There is no one class that specifically benefits from jewelcrafting so this can be a good profession to drop on a character that doesn't really have any use for a specific profession.
Jewelcrafting is best combined with mining. A lot of the items require either specific gems that can be prospected from ore or requires bars of specific metals. Mining also has the advantage of producing gems whilst mining and as a result definitely is the skill to take with jewelcrafting.
Enchanting / Disenchanting
A tremendous stand alone skill that can start paying off almost immediately. Unfortunately you can't make a dime by enchanting things but you can make a killing disenchanting things.
At about 300 enchanting skill it's possible to disenchant pretty much any item currently in the game for various shards and essences which can be sold for good profit on the AH.
Enchanting itself doesn't pay money until you have a few popular formulas. Early on anything that enchants a weapon with some form of glow (beastslaying, fiery, icy etc.) can be turned into a decent profit and later on there's a few popular enchants that can drag in some cash.
Unfortunately since you can't pawn off enchants on the AH it requires a certain amount of activity on the trade channel to turn enchanting into a profit.
Disenchanting however will always be profitable. Scour the AH for items that are sold below their average disenchant value (addons like enchantrix can show the estimated disenchant value of an item), disenchant them and sell the result for a profit.
Enchanting / disenchanting is one of the best skills to have sitting on a bank character (if you have one of those).
Anything that fuels your disenchanting is useful. Leatherworking, blacksmithing and tailoring all produce a decent amount of green items during levelling that can be disenchanted but of these only tailoring doesn't require a resource gathering skill to fuel it.
Note that in case of picking enchanting with a crafting skill often results in your disenchanting skill being used to cope with the losses you generally incur through crafting.
Engineering is a high utility skill. Some of the most fun items in the game come from engineering and it is often one of the most popular professions for PVP oriented people.
Engineering doesn't make you money but it does help increasing the overall utility of your character. A good example of this is engineering on a paladin. Paladins really don't have a good way to 'pull' mobs other than walking into their aggro range. Slap on Engineering on a paladin and you gain a number of options to pull enemies from a distance like EZ-throw dynamite.
Much like blacksmithing engineering requires a good amount of ores and as a result is best combined with mining.
Alchemy is a good all-round skill. The various potions can be used to buff run-speed, stats and grant various other effects and is the primary supplier for the ever-popular healing potions and mana potions.
Since most potions do not require you to have alchemy to use the potion it is very much possible to have alchemy on a single character and use it to supply the rest of your characters. Alchemy is a very decent skill for potion dependant classes like cloth wearers (not warlocks) but can be considered useful for most any class.
Alchemy _can_ make you money provided you have the recipes for high level mana / health potions. Since these potions are usually in high demand a profit can be made fairly consistently provided you spend the time farming the necessary materials.
Alchemies counterpart is Herbalism and they make a decent team at that. Especially at higher levels where certain plants always seem to be sold out on the AH it can come in handy to have Herbalism to pick up the necessary plants.
Mining is without a doubt one of the most popular professions within WoW and for good reason. Ore is always needed by Engineers, Blacksmiths, Jewelcrafters and the side product of mining (gems and motes) are essential parts of some tailoring and leatherworking recipes. As a result whatever you mine with mining can be sold on the AH for a decent profit.
When in doubt, mining is the skill to pick.
Herbalism is the engine of the Alchemy profession but beyond that has some utility in other crafting professions simply because higher level recipes will often require a herbalism component. Unlike mining however not all herbs can be sold for a significant profit. Nonetheless Herbalism is a gathering skill that can bring a substantial income provided one farms the right herbs. More often than not it becomes possible (starting in outland) to 'herb' certain killed mobs as well increasing the profit one can make by killing stuff.
Skinning is without a doubt one of the most straight forward gathering skills. Unlike mining and Herbalism you don't have to spend your days running around a zone looking for little yellow dots on your minimap. Instead you simply skin the beasts you kill. The only caveat here is that you can only skin certain animals and as a result it's worth the time to find something that is skinnable when going out to kill stuff.
Skinning can be used to make a fair amount of money since Leather is often a pre-requisite for tailoring / blacksmithing recipes and of course in high demand with leatherworkers.
First aid is considered to be a must have for any class. The ability to quickly heal up in between battles and sometimes even right in the middle of battle can be priceless. Even though you can drink / eat / quaff potions and do a number of other things to regain your health there's never a good reason not to want to be able to heal more. The profession is easy to level up and will definitely pay off.
Fishing is a rather time-consuming sport and is often disregarded. Nonetheless some of the best food-buffs come from fishing and quite a few recipes in the alchemy department have some fishy components. Fishing a little every now and then can be beneficial but it's by no means crucial to pick this up during leveling up.
Being able to cook up some raw components into edible food can be beneficial for specific food-buffs. In the most cases the utility of food-buffs isn't all that relevant before the higher levels so the time invested usually doesn't result in any 'significant' payoff.
However if you are interested in food buffs then levelling fishing together with cooking is very much possible and a very good idea.
On a side note. If you're interested in how popular certain professions are take a look at the image below .
The image is about a half year old and the low popularity of JewelCrafting can in part be explained away by the fact that it is a fairly new profession (TBC).
As always take the popularity chart with a grain of salt since it should not be assumed that since profession x is higher in the list it must also be better...