You can improve you skills by either going to the trainer and buying the App2 version or going to the broker in your tradeskill instance and buying the App3, App4, Adept1, Adept3 or Master versions of these skills. The great thing is that you do not have to go up step by step. You can go right from App1 to adept3 if you have the money. When you become a Paladin, some previous skills will be replaced and some won't. Try Alla's website under Spells and skills. There is a complete listing of Paladin skills and you'll see what you'll be getting as you level. That should give you a general idea as to what will be replaced.
I recommend increasing all your Teir1 skills App4. These can still be found on the broker for 30s and under, depending on your server. Teir2 skills you should try to get App4 or higher. Preferably Adept1. Power Cleave, Demonstation of Faith, Righteous Blow and Righteous Anger can usually be found in Adept1 versions for 30s to 1g on most servers. This will really help you in your tanking ability. Especially Demonstation of Faith, as the Adept1 version is more power cost effective and the ward amount is double or more of the App1 version.
Also remember to upgrade your equipment to orange when you can. As a Paladin, you'll be getting beat on in very fight, so better equipment will make a big difference in your ability to outlast an opponent. Try for stuff with resistances as well. These can help make a deadly fight into something you can handle if your careful. In some cases, better equipment will be more important than skill increases.
This was one of the first questions I asked of my guildies, and their advice has made a huge difference in my tanking ability.
Hope this helps.