"What things can a paladin do?"

Healing: Holy paladins and off-specialization healing.
Holy paladins are the most efficient single target healer.
Protection or retribution paladins can still heal, they just need experience and good gear: This will occur in regular 5-man instances when the group leader decides that you are in need of a healer and raids where a healer needs support.

Tanking: Protection paladin, off-specialization tanking, off-tanking and trash tanking.
Protection paladins are the multi-target tanks.
Holy or retribution paladins can still tank, they just need experience and good gear: This will occur in regular 5-man instances when the group leader decides that you are in need of a tank.
Off-tanking is the description of a high stamina character in melee range in second place on the threat meter. The off-tank is there to absorb damage from the rarisim attacks.
Trash tanking happens in raids where random adds pop up, a holy or retribution paladin can easily tank these with righteous fury.

Damage: Retribution paladins and shockadins.
Retribution paladins are a damage build, so no explanation is needed there other than the fact that retribution paladins are not pure damage. If you want to top the damage meter, roll rogue. Retribution paladins bring many debuffs and buffs that will benefit the raid overall and helps the raid increase their damage output as a group. This includes Sanctity Aura being used to bring up a protection paladin's threat ceiling.
Shockadins are a 40/0/21 holy build. The two things to note here is that Holy Guidance increases holy damage, and Sanctity Aura increases holy damage done by 10%. This is not a raid welcome build due to the mana-inefficiency, but it is a viable option for soloing holy paladins or PvP holy paladins wanting to do burst damage.

"What profession is the best for me?"

From what I have seen and heard, if you are a new player with a new character with low money, it is best if you have mining and skinning to earn money and power level your crafting professions at level 70.

If you can spare the expenses, it is best to have two crafting professions at level 70:

Retribution: Blacksmithing and Engineering
Blacksmithing: Deep Thunder is considered an all around decent PvP and PvE weapon for beginner retribution paladins.
Engineering: Furious Gizmatic Goggles Is an amazing goggle that rivals T4 and T5 helms. Along with that, engineering provides many explosives and trinkets that will prove to be useful in PvP whether interrupting casts, preventing kiting, or just for fun.

Protection: Enchanting and Jewel crafting
Enchanting: Protection paladins can grind a lot of mobs and instances. Disenchanting the loot provides an excellent profit margin.
Jewel crafting: Tanking paladins will generally upgrade their armor more often than other classes, and a lot of gems are needed. This helps cut down the costs as well as access to Falling Star and Figurine - Dawnstone Crab

Holy: Alchemy and Enchanting
Alchemy: As a healer, you will have to have a nice stack of mana potions at your disposal.
Enchanting: Holy paladins will usually benefit the most from doing group quests and instances, and hence, you will have a lot of uncommon or rare quality loots. Disenchanting the loot provides an excellent profit margin.

"What weapon is the best for me?"

Retribution specialization prefers a slow, top-end damage, two handed weapon for Seal of Command procs and well as burst damage effects in PvP.

Holy specialization prefers a two hander before access to spell damage between the levels 1-60, but once tBC equipment becomes accessable, a high spell damage one handed weapon and shield combonation is prefered.

Protection specialization prefers two hander for single target mobs, but more often than not, a protection paladin will go after a high spell damage one handed weapon for multi-tanking (4+) and a warrior weapon for single-triple target tanking and a damage reflective shield and grind numeroase monsters at the same time.

Paladins have access to:
One and two handed axes.
One and two handed maces.
One and two handed swords.
Polearms.

"What stats should I be looking for?"
These itemization are based on grouped play. If you are solitary play or PvP oriented, add stamina to the list.

pre-BC itemization

Holy: Intellect and Stamina.
For mana pool and survivability.

Protection: Stamina and Strength.
For damage intake and threat generation.

Retribution: Strength and Intellect.
For damage output and mana pool.

tBC itemization
Although not completely in this order

Holy: Intellect, healing, spell critical strike rating, mana per 5 seconds.

Protection: Stamina, strength, (spell damage,) defense and other avoidance.

Retribution: Strength, Intellect, critical strike rating.

"Is cloth okay to wear?"

Cloth is about 1/8th of plate armor value.
Leather is about 1/4th of plate armor value.
Mail is about 1/2 of plate armor value.

As a paladin, you should be looking at 10000+ armor at level 70.

You have around 1000 armor value per peice of your armor.

That means mail is around 500, hence 500 armor reduction per piece of armor, and hence around 1% physical damage reduction loss.
Leather is around 250, hence you lose around 2% physical damage reduction loss.
Cloth is around 125, hence, around 3% physical damage reuduction loss.

This is not a significant loss for holy or retribution paladins; however, armor scales, and the damage taken scales rapidly with loss of armor.

This being said, if you are holy or retribution, you should not worry too much on the fact that you have armor below cloth. In PvE, and even in most PvP, you won't be the one taking the focus fire.
However, a protection paladin should never sacrifice even one peice of armor if possible.