King Arthur. Aragorn the Ranger. Joan of Arc. The Twelve Peers of Charlemagne. These are paladins—knights sworn to uphold a particular cause, holy warriors devoted to a deity or virtue, and the shiniest of shiny knights.
In D&D and other fantasy RPGs, paladins tend to be a hybrid warrior/priest class. Big swords, thick armor, loud boasts about good and justice. All that sort of thing.
Look at that posture. Clearly a paladin.
ABILITIES
Throughout the editions of D&D, paladins have been defined by:
1) Their divine abilities, which are similar but not quite the same as those of clerics. They tend to have a much more specific, restricted spell list. Paladins tend to be more specialized as healers (lay on hands, cure disease, etc). Sometimes they’ve been able to turn undead, sometimes not. 5e has made an effort to create paladins of distinct types, which has been largely effective (see archetypes, below).
2) Their fighting ability, which is higher than that of a cleric but not as high as that of a pure fighter. In 2e, paladins had full attack progression (better than clerics) but couldn’t specialize in weapons (as fighters could). Paladins are typically considered front-line fighters and off-role support, as their magical abilities aren’t quite up to being a dedicated support caster, let alone a designated controller.
3) Their smite ability, which has taken on various forms throughout the editions. In early editions, it was a limited # of times per day to gain a bonus to attack an “evil” creature. 3e broke it into more specific smites (smiting evil, smiting chaos, etc), and then 4e turned the smites into various encounter/daily abilities that could be used on any target (going along with the graying out of the alignment system). 5e has paladins sacrifice spell slots to cause additional damage on a smiting attack (any target), and paladins can also cast specific smite spells for specific effects.
4) A strict code of conduct…

So Lawful Good I ride a UNICORN, n00bs! (art by sandara.deviantart.com)
TO GOOD LAWFULLY OR NOT TO LAWFULLY GOOD
In the earliest editions of the game, paladins had to follow a very specific, very restrictive code of conduct and alignment. They had to be lawful good. They had to vow to support charity and smite evil and defend the weak and helpless and, well, be lawful good. And depending on how draconian your DM felt like being at the time, if you stopped being lawful good for as little as ONE SECOND–if you took one wrong step or did one wrong thing–then BAM, all those fancy paladin powers were out the window. You might be able to atone with a quest (story hook, anyone?) or you might just be a mediocre fighter for the rest of your gaming life. (Sucks about all those missing feats, brah.)
And as long as people have played with Truth, Justice, and the Faerunian Way sorts of Paladins, gamers have loved the concept of the EVIL paladin. The anti-paladin. The blackguard. The chaos paladin. The dark paladin. The death knight.
Some of them used to be paladins, and lore abounds with this “fall from grace” sort of story: paladins who made a mistake that cost them their powers, and they became twisted champions of evil. Lord Soth from Ravenloft, Scyllua Darkhope from the Forgotten Realms, Anakin Skywalker/Darth Vader from Star Wars. (Um, spoiler alert.)
Some, however, were always evil—were anointed by a dark god or swore their service to a foul depravity, rather than a virtue. And so was born the concept of the blackguard. The blackguard was a prestige class in 3e, which was mechanically similar to a paladin but evil—all their powers reveled in darkness, rather than good. 4e removed the alignment restrictions altogether, so you could play a paladin of any alignment—a holy warrior sworn to any cause—and produced the blackguard base class. 5e also has no alignment restrictions.

Lord Soth, for when Lawful Good just isn’t LAWFUL enough…
ARCHETYPES
At first, when D&D was young, the “knight in shining armor” sort of paladin was your only option. You had high strength, decent wisdom, and a punishingly high charisma requirement (2e required you to have a charisma of 17 to play a paladin). And then your character was basically a shining example to the world. Many people played paladins like self-righteous jerks who eventually crossed the rest of the party ,but a paladin doesn’t have to be that, even while being lawful good (see my post about Lawful alignments for more on this subject).
3e broadened the paladin’s horizons with an official blackguard prestige class, which is mechanically linked with paladins (basically, they have almost identical abilities, but themed for causing harm and evil, rather than healing wounds and good, down to a Smite Good ability). The rogue/paladin Shadowbane Inquisitor (ahem, gee, wonder if *that* was a coincidence) prestige class from Complete Adventurer also showed us that paladins could be something other than straight up fighters, while the Grey Guard from Complete Scoundrel gave gamers an avenue to bend the inflexible moral requirements of being a paladin in pursuit of a greater good.
4e allowed paladins of any alignment, allowing holy warriors of various causes, and also produced the Avenger base class, which is similar to a paladin in many ways (more like a rogue/paladin). 4e produced the Blackguard base class, which is kinda like a paladin, but different—more of a striker than a defender, an avenger rather than a protector.
5e has really delved into what a paladin could be other than the knight in shining armor and the dark champion of villainy. You can certainly play the classic, protector, valorous paladin, or you can play the paladin whose powers come from the land and who has sworn oaths to protect the ways of the ancients, or you can play a gritty, obsessed with vengeance upon their enemies sort of paladin. The archetype system in 5e is really a powerful tool for both mechanical and roleplaying opportunities.

The Paladin: calm, serene, noble–can kick your ass twelve ways to Sunday.