I was recently asked by a friend of mine about how to make a paladin. Paladins being one of my favorite classes in the game, I replied with the following advice.
Personally, I like to play paladins who are not "Lawful-stupid" they are beacons of light and the bastions of all that is good and right in a world of failed and flawed people. Taking the high road all the time and leading by example is the name of the game. As a Charisma-based character, paladins make great party faces.
Paladins to me, are warriors devoted to their faith people talk about for centuries. People such as Sir Percival, Saladin, Roland. Paladin-hood is a calling, it is a blessing you must prove yourself worthy of receiving. It's not about looting, it's about making the world better and evil weaker, but not by taking shortcuts, the ends are as important as the means and the journey matters. For what good is it to win the world, but lose your soul in the process? The paladin is the hero who rises to that challenge, who leads from the front and who people love and remember.
He is the knight who walks into the dragon's den knowing there is no way to win, but he does it because doing so means saving the village. He is the one who walks into hell and calls out "I'm here to clean up this place".
I guess the important thing to remember is what your role is: you are a holy warrior and a leader of men. You are somewhat self-sufficient through your abilities, but that should not make you into a selfish zerger.
You character doesn't have to be a jolly, happy dim-wit. He can have mood swings, be sad, be impolite, he can have a love for the bottle. However, he should focus on getting things done. He is the light in the darkness, not a sun surrounded by mirrors to look at his own awesomeness.
Building a Pathfinder Paladin
Although there are a million archetypes to do all sorts of things, I will focus on a single-class, corebook character wherever possible.
If you are talking about in-game build, you need decent to high Charisma, decent Strength, positive Constitution. Wisdom and Dexterity are second-thoughts and Intelligence is a dump-stat. (Though they are heroic, no one expects them to be overly bright)
Skills: You don't have a lot. Take a rank in Handle Animal, Ride and Knowledge (religion). For the rest, focus on skills you are great at such as Diplomacy and Sense Motive. Take all favored class in skill points.
Feats: I am partial to Power Attack and Step Up, but then anything that will tank up your AC (Dodge, Shield Focus), beef you up (Toughness), or help your attack (Furious Focus, Weapon Focus) are good.
Builds: Many favor the heavy armor/ two-handed weapon, which is a reliable build. A greatsword or falchion are my top favorite, but a polearm such as a glaive or a bardiche should not be overlooked. If you want to go sword and board, the longsword, battle axe or scimitar are good choices. Make sure you buy a sap to deal non-lethal damage and bring criminals to justice...
I built a light armor/shield/scimitar build in PFS that worked very well. The character met with a lot of derision and recommendation, all of them away from my own idea, and honestly more in-line with my own recommendations above. She didn't seem like much to start, but when a paladin's work was needed, she shone and kicked butt big time.
Regarding the mount... well it was great, but Paizo never gives us reasons to use them. The weapon bonuses have a much wider utility, so I would definitely go there. If you are playing in a home game or non-Paizo product, then you might get more usage out of the mount.