Gratz on 40!

There are a number of leveling guides on the internet. This is an extract from one at TenTonHammer.com

40-50] Forty to Fifty

Zones Visited
Badlands
Desolace
Tanaris
Feralas
The Hinterlands
Blasted Lands
Felwood
Un'Goro Crater

Instances Visited
Scarlet Monastery
Uldaman
Razorfen Downs
Maraudon
Zul'Farrak

Related Guides

* Instance Encylopedia
Need info an instance? Find it here!

Questing

At level forty, assuming you're almost done with STV, you can head to the Badlands and get to questing. There isn't much there Alliance wise, but there should be enough to get you to about 41 with what is left of STV. At 41, the Alliance can venture into Swamp of Sorrows for a good bit of quests before returning once more to Desolace. When you're about done there, head on out to STV again to once and for all be done with it.

By now you should be 43, so head out to Tanaris and Gadgetzan. Your not going to complete all the quests here, but you can get a good few done. Enough to get you through level 43 that you can probably hit 45 once you start Feralas. Feralas is an annoying zone, but has plenty of quests to get you through to about level 45.

Now here is the thing about Alliance, once you get to 45ish you're going to be in a situation where all of your quests aren't very good. You've got a few options. One is to grind and the other is run Uldaman. I suggest going ahead and running Uldaman. It's an annoying instance and completely skippable, but it should be enough to get you to 46 which with new skills makes things easier.

Speaking of level 46, this is about the time you can start The Hinterlands. For Alliance this is a pretty good zone and is enough to get you to 47 (which is about the point you can finish or at least do more of Feralas). At 47 you can return to Tanaris to grind out the higher level quests that you probably couldn't either get at 43 or couldn't finish. By now you should be 48. Now, there is a few options here. There are a ALOT of level 43-45 group quests in STV that should be green and almost grey by now. These should be soloable, like Big Game Hunter. If you done them with a group earlier then that's cool as well. XP is XP no matter the level (unless the quest is grey).

Now, assuming you're 49 you can probably start the Blasted Lands. If not, get some instance runs down! Zul'Farrak and Razorfen Downs are worth the effort and if you didn't do Scarlet when you hit 40 then get that done as well.

Grinding

You will most then likely find yourself questless around level forty four or forty five with the quests being either too annoying to do or just lacking in anything worth while. So you’ll probably find yourself grinding out a few levels, don’t worry though there is plenty to grind on!

At level forty you can start grinding on all of the Wastewater Bandits in Tanaris. Pirates are always great to grind on since, like pirates they just melee at you or shoot at you with a gun! Nothing special. There are also the Whelps in the Badlands which can take you up to forty three. Elementals in the Badlands are also good for grinding (and good for cash). At later levels, the harpies in Feralas provide excellent grinding material.