Getting to level 40 is probably the second marker you want to achieve as this is where you will be able to obtain your next mount.

You should by now be pretty comfortable with your characters skills and your role playing identity will be developing well. Start thinking about how you will spend your next amount of talent points which will allow you to play with ease. If you have spent your talent points wrongly then now would be a good time to correct them. It will cost 1 gold and you should not need to change them again as long as you chose correctly. Get the addon 'talented' as this will allow you to design talent templates without the worry of using your points up.

To level yourself up to 40 we need to follow the same principles of minimising downtime, here are the zones I would recommend you do:

Alliance

Redridge Mountains
Duskwood
Wetlands
Ashenvale
Stonetalon Mountains
Thousand Needles (do not forget to check out Mirage Raceway)
Stranglethorn Vale
Hillsbrad Foothills
Desolace
Dustswallow Marsh

Horde

Stonetalon Mountains
Hillsbrad Foothills
Ashenvale
The Barrens
Thousand Needles (do not forget to check out Mirage Raceway)
Stranglethorn Vale
Arathi Highlands
Alterac Mountains
Desolace
Dustswalow Marsh

You are going to need to circuit these zones maybe more than once on separate visits, as quests will range in level requirements. Pick up those that turn green in your log only doing yellow ones if your confident enough to do so; however if you plan your circuit well enough then upon your return they will be green and much easier to do. The easier the circuit you plan the quicker it will go as wasting time on death or taking too long on quests will slow your levelling down.

If you have not already done so getting the addons 'cartographer' and 'liteheaded' which will help you plan your circuits more efficiently.
Cartographer will use your in game map to plot coordinates so you can plan journeys for questing with ease and liteheaded will have quest information that will be indispensable for your levelling journey.

If you have a high level friend possible guild mate who has a choppa/hog or a traveller's tundra mammoth ask them to take you by road to pick up the zone fly points, this can potentially save you bags of time during levelling between 20 and 40.

Bag space is going to be imperative during this phase as your going to be picking up quite a few items. Most will be junk, however there will be meat and cloth for your secondary skills together with whatever items you pick up for your primary skills. Cutting down on time spent going back to sell items is a must, so obtain as much zone information as possible. There are some traders dotted around in other locations in some zones so it would be worthwhile looking these up and marking them on your map using the notes function of cartographer. If you are lucky enough you may obtain a world drop of a rare or epic quality so the last thing you want is no bag space.

A point to note is that some quests will take you to the cities. Try to time this with training, banking and checking the auction house. When in the cities check if there are quests available to pick up for future areas you are about to do as these can usually reward some nice Xp.

Some of the quests will require items which you will need to either craft or buy from the auction house. What I normally do is check a zone ahead of my character going there and buy then bank the items. Another method is to buy the required items with your bank character then mail them to you.

Here is a list of items you will need for some quests whilst you level between 20 and 40 that can easily be missed hence waste time obtaining.

Alliance

10 Lean Wolf Flanks - level 27; Duskwood
1 Bronze Tube - level 26; Duskwood
60 Wool Cloth - level 30; Darnassus, Craftsmen's Terrace
4 Lesser Bloodstone Ore - level 32, Stranglethorn Vale
10 Turtle Meat - level 31; Thousand Needles (do not worry if there are none on the AH it just means you will have to kill Turtles)
Keep any Green Hills of Stranglethorn pages - level 32; Stranglethorn Vale
1 Soothing Spices - level 35; Hillsbrad Foothills
Elixir Of Fortitude - level 38; Dustswallow Marsh (you will get this as a quest reward, keep it for a later quest)

Horde

Keep any Shredder Operating Manual pages - level 22; Ashenvale
1 Deadly Blunderbuss - level 26; Ashenvale
10 Turtle Meat - level 31; Thousand Needles (do not worry if there are none on the AH it just means you will have to kill Turtles)
Keep any Green Hills of Stranglethorn pages - level 32; Stranglethorn Vale
1 Soothing Spices - level 35; Hillsbrad Foothills
1 Elixir of Water Breathing - level 37; to aid with a quest in Desolace

Quests to Note

Alliance

*A Watchful Eye (Elywnn Forest) - Starts at the Tower of Azora on the road between Elwynn Forest and Redridge Mountains.
*Elune's Tear (Ashenvale) - This quest has a chain. There is approximately 15 seconds of text before the next parts become available so do not run off too quick or you will miss a quest.
*Blisters on The Land (Wetlands) - Fen Creepers can be found in the shallow waters and are stealthed.
*Missing In Action (Redridge Mountains) - This is at the northern edge at Render's Rock where this is a cave entrance past some mobs. Once inside the cave stick to the left until you reach a room with a big pool. Clear the way and take the escort quest. The mobs here are close together so once outside the cave, he will stop to rest. Pull the camps yourself when you get outside or your escort will pull the lot.
*The Wanted Tharil'zun and Gath'llzogg (Redridge Mountains) quests may require a group depending on how skilled you are. I have done these solo however when I first started I could not.
*Wanted: Lieutenant Fangore (Redridge Mountains) - Try to get around the mobs on the west side and position you behind him. There is group that is near him so wait until he walks away from them and pull 1 or 2 and move backwards while fighting. Remember these mobs run when about to die so use any slowing, root or stun ability.
*The Cursed Crew (Wetlands) - Enter the boat through the hole in the side which is partially submerged in the water.
*The Lost Chalice - When you hand this in there may be up to a 30 second delay for game text from a different quest just handed in.
*Hints of a New Plague?part 2 (Arathi Highlands) - You are looking for a Forsaken Courier and several bodyguards. You have to kill the Courier and loot the envelope by using some means to distract the guards. The courier wanders on the road throughout the zone.
*Recover the Cargo! (Dustswallow Marsh) - If you are having difficulty locating these underwater they can been more clearly from the surface.

Horde

*Vorsha the Lasher (Ashenvale) - Make sure you follow Muglash or the quest will fail. You will be taken to a brazier where you will have to fight 3 waves of mobs. Vorsha will be in the 3rd wave. If you die, do not release, the NPC can sometimes finish him off without you and you will get credit for the quest.
*Freedom to Ruul (Ashenvale) - This is an escort quest from a cave full of Thistlefur Avengers and Shamans and can be tough as they respawn quite quickly. Once outside try to control the pull as the NPC your escorting will more than likely pull entire camps.
*Torek's Assault (Ashenvale) - Protect Torek or the quest will fail. Let the other Orcs take the mobs.
*The Tear of the Moons (The Barrens) - You have to kill a level 30 NPC who has other mobs around. Root, sap, stun and focus on the level 30. If you die run back in resurrect, loot quickly and pop a health pot. Without the level 30 the other mobs can be handled quite easily, just do not panic.
*Sharptalon's Claw (Ashenvale) - You can lure him to the Forsaken camp who will assist in the attack. Just make sure you do most of the damage so you get the loot.
*Battle of Hillsbrad Part 4 (Hillsbrad Foothills) - Clear the first 2 rooms, then pull the 1 mob which is on the left inside the room. Go back to the room behind you and hide behind a wall. This way the Councilman cannot shoot you from a distance but instead come to you. Then go to the big room and kill Clerk Horrace Whitesteed. Get back to full health then kill Magistrate Burnsidethen. Finally, destroy the Hillsbrad Proclamation and collect the Town Registry.
*Battle of Hillsbrad Part 5 (Hillsbrad Foothills) - Foreman Bonds at 20% health summons 2 dwarves to guard him and they can stun you, so ensure you have a clear escape route if things do not go your way.
*Homeward Bound (Thousand Needles) - Watch out for a rare elite called Heartrazor. You can sneak past at the right moment however since you have no control over the NPC your escorting you may find this difficult.
*Helcular's Revenge (Hillsbrad Foothills) - Watch out for the guards they are much higher in level, will aggro easily and kill you.
*Gelkis Alliance (Desolace) - Take this quest not Magram Alliance.
*Questioning Reethe (Dustswallow Marsh) - You will have to deal with 4 level 35-37 NPC's although the orge can take 1. Sometimes if you hit one just as the combat starts 3 will go for the orge, it has happened a few times for me now. Be sure to kill quick and not let the ogre die.

Items to Have

Make sure you keep a steady supply of health and/or mana pots as these can be invaluable for those near death moments. Have enough food and/or drink so you can top up your health/mana after combat. Use your cooking skill as you progress as most buff food always gives a stamina bonus. Keep a stack of bandages in your bags to top your health up. Check what areas you are going to quest in and buy some potions or elixirs that can aid you i.e. swim speed, water breathing, attack and spell power pots can improve your levelling time.

Professions

Keep doing your secondary skills first aid, cooking and fishing as these can assist you whilst levelling. Most primary skills will also have items you can craft that can benefit you whilst levelling like potions, armour or weapons.

Dungeon Instances

If you can get a group together you may want to try your hand at some of the instances you are going to be near. There is some nice Xp and gear to be had. Below is a list with level and location:

Wailing Caverns / 15-21 / The Barrens

Shadowfang Keep / 18-25 / Silverpine Forest

Blackfathom Deeps / 20-27 / Ashenvale

The Stockades / 23-26 / Stormwind (Alliance only)

Gnomeregan / 24-33 / Dun Morogh

Razorfen Kraul / 25-31 / The Barrens

Scarlet Monastery / 30-40 / Tirisfal Glades

Razorfen Downs / 35-40 / The Barrens

Uldaman / 35-45 / Badlands

How you should level is all about what makes you feel comfortable whilst getting the highest level of enjoyment out of the game. Everybody levels at a different pace. I level slower than some of my friends because I want to experience battlegrounds, ensure my professions skill up, follow the game lore and take in the wonderful game scenery. However I am not usually far behind them and because I have done extra with the professions and built up honour points my gear and gold made tends to be far better.

Again I can not stress enough the importance of not buying power level or gold services as Blizzard will terminate your account if they discover it. Also most of these services are game hackers so using these services supports them to the detriment of fellow players.