Levelling Tips

[Muridin]

First Steps
Starting out as a newbie in Elwynn or Dun Morogh is pretty much the same as any other class, but you'll start to see why Paladins feel so strong compared to other classes. At this point, your damage will be the same as anyone else, and you'll enjoy having good heals. Your trainers will be inside Northshire Abbey and behind the Blacksmith in Goldshire if you're human, and inside Anvilmar and inside the inn in Khranos if you're a Dwarf. There's nothing really tricky about the first 10 levels or so - do every quest you see, save your money if you're a newcomer, and you should be able to get 10 within a few hours.
Once at level 10, you're going to get your first talent point. I normally offer new players a choice at this point when they ask me - Go for Divine Favor or go for Seal of Command. With 1.9, it's not even a choice anymore - go for Seal of Command first and then plan to work your way up to Vengence. Consecration is helpful, but not required unless you're a dedicated tank for your group at the low levels. Blessing of Kings just isn't that good at level 20.
I don't think I really need to go into detail for the first twenty levels - if you're new the game, and need help, I would suggest reading your quests and meeting new players to help you get around the first few areas. Regardless if you're a dwarf or a human, though, I would start to do Deadmines in Westfall around level 17 or so. I will mention that around level 12, you'll want to go to the Stormwind Cathedral for the quest to get your resurrection spell.

Verigan's Fist
At level 20, a new quest will open for you - it starts in the Cathedral of Light in Stormwind and will be one of the most important quests in your young life - the quest for Verigan's Fist. This will be one of your most prized possessions, as you will be able to use this weapon for at least into your early 30s, and perhaps beyond depending on your luck in Gnomeregan. While I don't want to give a full spoiler, I will mention a few helpful hints;
•   When helping Daphne Stillwell, don't underestimate the dear lady, as she comes armed and will defend herself. She also will not go down immediately if one of the bandits starts to attack. Chivalry is great, but this is a frontier woman, and she's tough as nails. Retribution Aura is great - having Seal of Command will help a bunch too. If you're nervous, have a friend help, but this step is not hard. Keep your head and don't get overwhelmed.
•   The Deadmines part you can do with a normal group, the wood is a drop off any of the goblins.
•   You can solo the part in Loch Modan, just be careful and patient, and you can sneak by the ogres. The box is on the ground behind a tree in the middle of Mo'Gresh.
•   Blackfathom Deeps and Shadowfang Keep can be tricky, bring a friend. If you're on a PvP server, you're going to have to enter Horde territory to get to SFK. The gem from Blackfathom is outside the instance and is a random drop from the Satyrs and Naga there.

The Quest Continues...
Beyond level 20, the Wetlands, Duskwood and Ashenvale are good. Quest where ever you want to if you want the faction for early on - as a human it can really add up. At the late 20s, with Verigan's Fist, you will be owning undead in Duskwood. This is probably the high life for a Paladin, when you can do it all. In the 30s, you will have nearly countless quests to do in Stranglethorn Vale, Gnomeregan opens up, as does Scarlet Monastery, your new home for a few levels.
Scarlet Monastery is a source of amazing items for you, and you should get into the instance as soon as you can. For the Graveyard and Library, level 35 is enough, however, for the Cathedral, you should be level 38 or 39 at the least, and even then, you'll have a tough time keeping up with some of the harder hitting Scarlets. Items to look for here; Ravager, Aegis of the Scarlet Commander, Mograine's Might, Raging Berserker's Helm, and Herod's Shoulder. However, a quick look through Thottbot will show that there are plenty more items here for taking - this place is still popular with the level 60 crowd that is hunting for money, so you might be able to get lucky and have a higher level take you along to get some BOP items. Don't count on it though.
Into the 40s, you should have a pretty solid idea of what's coming for you. Your relative power will start to wane, but you can still be an accomplished tank if you play with a good group. Feralas, Desolace, Maraudon, Uldaman and Tanaris all open to you. Zul'Farak will come into play into the late 40s (be happy that you saved that Ravager, that's all I'm saying!).
At this time, you should be feeling the hurt in terms of training and buying platemail armor - the AH can be nice to gear up, but don't spend all your money there. Look for items from quests and drops from various instances and get your friends to help out and run them through. You learn a lot about your class in an honest 5-man run - you should get a lot of practice during the 40s and 50s for later on. You can get good money, get outstanding gear (for example, at 60, I'm still using the Gemshard Heart and the Hypertech Buckler was my main shield until the Sacred Protector. Both pieces are from Maraudon.)
Some quests that you should definitely look into while leveling up; The Scarlet Monastery main quest ("In The Name of the Light") is one of the best quests you can do as Alliance, and the Sword of Serenity is one of the best one handed weapons for its level. Maraudon also offers outstanding quest rewards in the Mark of the Chosen (from "The Pariah's Instructions") and the Thrash Blade ("Corruption of Earth and Seed").
At the high 50s, the Blightcaller quest, "Order Must Be Restored" yields one of the best shields you'll see pre-MC. You'll need a lot of friends to pull it off, though.