Patch 2.3 is more than just Zul'Aman, easier to acquire heroic keys, ret pally buffs, or the disappearance of the hunter dead zone. It's a chance to take advantage of all the Azerothian leveling changes by breaking out that sporadically-played alt and finally making the push to 58. But wait! Before you drop everything and head to Dustwallow Marsh, have you looked at your talents lately? Did you know what you were doing when you put that spec together, or were you just filling in points haphazardly? Now's the perfect time for a tune-up, so if you've got a mage alt in the wings, let's talk pre-Outlands talent trees.
Keep reading for my rationale on what talents to take when for each spec, or just use the links below to hop straight to a talent calculator for my recommendations for arcane, arcane/fire, fire, or frost leveling specs.

Arcane
Ten points in arcane has long been a favorite start for fire and arcane builds alike, but it's only since the Before the Storm patch that arcane has become more than just a support tree. You can actually put together a really solid leveling build of arcane talents, but after 45 points, I strongly recommend you take a look at expanding into the fire tree. Here are my thoughts:
Your first five points should go into Improved Arcane Missiles, and your second five into Arcane Concentration for clearcasting. From there, pick up 2/2 Magic Attunement (and remember to keep Dampen Magic up while you're soloing) and 3/3 Arcane Impact, which will give you enough points to fill out 3/3 Arcane Meditation (after patch 2.3, this will give 30% mana regeneration in combat instead of just 15%). Put two points in Improved Counterspell, and you'll have opened up Presence of Mind. Snag it (and start using it for insta-fireballs), and you should now have your talents set through level 30.
If you're continuing straight down the arcane tree, your next stop is to max out Arcane Mind for a 15% intellect increase. Put your next three points into Arcane Instability, then one point into Arcane Potency, which lets you take Arcane Power. At this point you're level 40 with a lot of great talents at hand, but the very first thing you should be dumping points into is 3/3 Empowered Arcane Missiles — this talent is critical to real arcane dps, so take it first, and then stick your two points into Spell Power. From there you can put 4/5 into Mind Mastery, pick up Slow, and then hop back up to finish the 5/5.
You're now level 51, and you've got some choices to make. Find yourself fighting mobs a good bit higher level than you? The first tier talent Arcane Focus can increase your +hit with spells by up to 10%, but in my mind, it has marginal returns for leveling mages after 3/5 points due to the nature of the spell hit mechanic. Grouping more often, and finding yourself with uncomfortable amounts of aggro? 2/2 Arcane Subtlety will reduce your arcane spells' threat by a whopping 40%. If it were up to me though, I'd stick my last seven points into the fire tree if I hadn't gone arcane/fire already. 5/5 Improved Fireball followed by Ignite will increase your flexibility, and get you that much closer to the dreaded Arcane Power-POM-Pyroblast.


Arcane/Fire
Although I discuss dropping a few points into fire at the end of the pure arcane build, this build is aimed more at the mage who wants the mana regen benefits of arcane while casting a lot of fire spells. It's a solid combo for steady, efficient leveling, although in my mind there's a real advantage getting deep into a tree early on. Here's how it looks:
Put your first ten points into Improved Arcane Missiles and Arcane Concentration. Every time clearcasting procs, you should use it as an excuse to cast AM. Follow that up with five points in Improved Fireball and five points in Ignite, then swap back to arcane to pick up 2/2 Magic Attunement (again, keep Dampen Magic up while you're soloing), 3/3 Arcane Impact, 3/3 Arcane Meditation, and 2/2 Improved Counterspell. You're now specced through level 30, and your next two points will give you a powerful combo: Presence of Mind and Pyroblast. Use them together and use them often, but don't wait until your target is almost dead to use them -- most of the power of Pyroblast is in its DOT, after all.
You're now done with arcane and can go back to the fire tree. At this point I recommend increasing your range with 2/2 Flame Throwing, followed by 2/2 Incinerate and 3/3 Master of Elements. If you're experiencing a lot of pushbacks, you could take Burning Soul, but since you already have un-interruptable Improved Arcane Missiles, I suggest trying to change your playstyle instead of your build. Next, 2/3 Improved Scorch will open up Blast Wave, which is an awesome AOE talent. Drop your next three points into Critical Mass, and then finish out that last point in Scorch. Three points in Fire Power will take you to level 58, and from there it's on to Outlands.

Fire
Fire builds are all about raw damage — when you're playing a fire mage right, you should be able to kill your target in two or three shots, preferably before it even reaches you. The main challenge to doing this successfully in Azeroth is the lack of real +damage gear. (Fire scales extremely well with +dmg, which is part of why 10/48/3 is such a well-liked PvE spec.) That plus the fact that most pre-Outlands play is now soloing is why I tend to think frost is the strongest leveling build at the moment, but that doesn't mean fire can't be for you. If you don't mind drinking or dying a bit more often and enjoy lighting the furry creatures of the forest on fire, this spec can dish out a ton of damage and be a lot of fun to play. Here's how I'd build a fire mage:
Take 5/5 Improved Fireball and 5/5 Ignite, then snag an extra 6 yards of casting range with 2/2 Flame Throwing. Put your next two points into Incinerate, then pick up 2/2 Burning Soul to reduce pushbacks for when you can't quite kill a mob before it's beating you in the face. Improved Scorch and Master of Elements are the next talents to consider, and the order in which you take them is somewhat playstyle-dependent. Imp Scorch gives a lot of value for very little mana, but stacking scorch debuffs just isn't practical while soloing same-level regular mobs (it takes too long; they die too quickly). So it's a nice talent to have, but I'd put my first three points here into Master of Elements, then one point into Imp Scorch for now. This opens up Critical Mass at level 30.
Once you've taken 3/3 Critical Mass, I'd hop one more tier up and pick up Pyroblast so that you can take Blastwave next. (Yes, we could've taken Pyroblast earlier in this build, but it's a long, slow, mana inefficient spell that doesn't really shine while leveling unless you have Presence of Mind.) At this point you have two new talents open: Fire Power and Blazing Speed. Blazing Speed is fun, and a great PvP talent, but in my mind it's a distraction from the awesome dps talents we're working our way down towards. (Plus, you didn't roll a fire mage for the surviveability anyway, did you?) So take 5/5 Fire Power instead, and then pick up Combustion at level 40. From there I'd grab 3/3 Pyromaniac and put a first point into Molten Fury, which opens up the talent we've been working our way down to: Empowered Fireball. Max it out, and you can then pick up Dragon's Breath.
Finish up the bottom of the fire tree by putting your 42nd point into 2/2 Molten Fury, and now it's time to make some choices. Find yourself drinking a lot and/or fighting mobs a good bit higher level than you? You could hop over to the frost tree and put three points in Elemental Precision, an excellent talent that will increase your +hit with fire and frost spells by 3%, and reduce their mana cost by the same amount. Think you'd like a stun talent like the shadow priest's Blackout? 5/5 Impact is for you. Still want to play with Blazing Speed? Now's the time to pick it up.


Arcane/Frost
If you ask me (and you are reading my blog, after all), arcane/frost is a silly leveling spec. Frost is mana efficient enough on its own, so why go dumping ten points outside the tree? I'm told some people do it so that they can use AM on clearcasts, but the occasional free arcane missles just doesn't seem worth the cost to me. If you're determined to try it out, go ahead and put ten points into Imp Arcane Missles and Arcane Concentration, then use my frost spec to work your way down towards Ice Barrier, which you won't get for another ten levels because you decided you really wanted clearcasting, you fool!

Frost
I've never leveled as a frost mage, but when my boyfriend asked how he should spec his mage alt, I had no reservations telling him to go full frost. (He's level 69 now, and will be respeccing to fire at 70.) With Azeroth increasingly becoming a land of solo quest grinds, frost's control, survivability and mana efficiency make it a real winner for pre-Outlands leveling. Some talent guides out there are still focused on AOE grinding, but if you ask me that's 1) boring and 2) going to be much less XP efficient with the increase to quest XP in patch 2.3. So I'd spec a frost mage like this:
Five points in Improved Frostbolt gives you a primary source of dps. Next grab 2/2 Improved Frost Nova, and 5/5 Ice Shards. Three points in Piercing Ice opens up Shatter, and once you put five points in it you'll have a 50% chance to crit any frozen target. It's one of the critical talents in the frost tree, so pick this up as soon as possible. You're specced up to level 20, and have four excellent options to dump points into: the slowing talent Permafrost, the Frost Nova-like proc Frostbite, the mana/threat reduction talent Frost Channeling, and the increased range talent Arctic Reach. You'll want all four of these, but since I have to pick an order, well... take Arctic Reach first, then two points in Permafrost, then 2/3 Frostbite, then 3/3 Frost Channeling. We'll come back to finish off Permafrost and Frostbite, but before we do, at level 40 it's time to pick up the frost mage's favorite friend, Ice Barrier. Take Ice Block (fairly useless for solo grinding), then Ice Barrier. Add your new shield to your bar, and keep it up as much as possible.
Okay, got Ice Barrier going? Good. Hop back up the tree and stick those last two points into Frostbite and Permafrost. You could also pick up Cold Snap at this point, and to be honest, many frost mages seem to like it, but I just can't see a 10 minute cooldown being worth a whole talent point for a leveling mage, so I'd put your next two points in Ice Floes instead. This will open up Empowered Frostbolt; max it out. Level 50 gets a bit lonely grinding out in the Blasted Lands all alone, doesn't it? I thought so, which is why I'm having you put your next point into Summon Water Elemental, the frost mage pet. Aww, isn't he cute? He's on a three minute cooldown, so you can use him as an emergency tank or a damage boost.
We've worked our way down to the bottom of the tree, but there are still valuable talents aplenty in it. Elemental Precision is a good choice for your next three points, and I'd choose Arctic Winds for your final five.
Congratulations, you're 58! Go kill some hellboars.