Planeswalker card types were introduced in Lorwyn.
A brief overview... What is a Planeswalker?
Planeswalkers enter the battlefield with a set number of loyalty counters, printed in the lower right of the card. A planeswalker can be attacked, like a player, or be dealt damage by an opponent redirecting the damage one of his or her spells would deal to the player controlling the planeswalker. Damage dealt to a planeswalker removes that many loyalty counters and a planeswalker with no loyalty counters is put into the graveyard.
Planeswalkers usually have three abilities: one ability that adds loyalty counters as a cost for a small benefit, one that removes a small amount of counters as a cost for a larger effect, and one that removes a large number of loyalty counters for a big effect. The last effect is commonly referred to as the planeswalker's "ultimate" ability and usually leaves the opponent in a devastated state. The starting loyalty of a planeswalker is commonly significantly lower than the cost of its ultimate and a player has to build up the loyalty to access it.
How do I use it?
When you control a Planeswalker out on the field, you may use one ability on your turn, whenever you could cast a sorcery. When you choose an ability, the number next to it is added/subtracted from its loyalty counters. You should always remember to make sure the number of loyalty counters does not go down to zero or less, or else your Planeswalker will leave the battlefield.
Now how do I get rid of them?
Another way to think of a Planeswalker is as another player that is under its owner's control. However, a Planeswalker's options are limited to the abilities on the card. The Planeswalker also has a "life total", like any other player would (In the form of loyalty counters). That life total can increase by using the (+) abilities, and decrease with the (-) abilities, as well as by taking damage.
One way to eliminate a Planeswalker is to attack it instead of its controller's life total. Its controller can block with creatures in the same way they could if you attacked them. Any damage that isn't blocked is subtracted from the Planeswalker's loyalty counters. If the loyalty counters on a Planeswalker reach 0 (or less) that Planeswalker is put from the battlefield into the graveyard.
If a player controls a source that would deal damage to a player, they may instead elect to have that damage inflicted to a Planeswalker that player controls. The damage cannot directly target a Planeswalker, but instead must target the player, and note that you are redirecting the damage to a specific Planeswalker that player controls at the time the damage would be dealt. This may sound confusing, but basically any spell that would deal damage to a Player can be redirected to a Planeswalker that Player controls. You must specify where the damage would go at the time you cast the spell. The purpose of this is so effects can be used to negate, amplify or redirect the damage such as if the Player had Hexproof, in which case you'd have to kill their Planeswalker with combat damage or an area of effect spell, or cast a spell like Safe Passage which would prevent the damage from being dealt to them, therefore making it impossible to redirect the damage to their Planeswalker
Cards that affect creatures do not affect Planeswalkers. For example, you could not eliminate a Planeswalker with a Doom Blade as it says "Destroy target non-black creature", however you could damage them with a Shock as it says creature or player.
Also, if two Planeswalkers with the same sub-type are on the battlefield, both go into the graveyard from play. For example, if your opponent had Chandra, the Firebrand out and you cast Chandra Nalaar both would be put into the graveyard, as the have the same subtype, Chandra. It's not the preferred method, but it is a way to get rid of opposing Planeswalkers. This rule has been modified at the start of the Magic 2014 core set release.
An example of using a Planeswalker
Hopefully this will make it easier to understand.
You cast Liliana Vess on your turn. She enters the battlefield with 5 loyalty counters on her. You then proceed to to use her +1 ability (as Planeswalkers are not affected by summoning sickness) put a loyalty counter on her and cause your opponent to discard a card. You then do whatever else you wish and it becomes your opponent's turn.
Your opponent begins his turn, having a Shock and a Terminate in his hand. The Terminate couldn't affect your Planeswalker as it says creature not Planeswalker. However he may attempt to cast the Shock targeting your Planeswalker instead, which he does. You then cast a Safe Passage preventing the damage. Your opponent then attacks with three 4/4 creatures, sending all of them at Liliana Vess. You manage to block all but one, causing 4 damage to hit your Planeswalker reducing its loyalty counters from 6 to 2. Your opponent finishes his turn and passes it to yours.
You begin your turn and do whatever you wish, then must decide on what ability to use on Liliana Vess. You could use her +1 and bring her loyalty counters up to 3, or use her -2 and bring her loyalty counters to 0, causing her to leave the battlefield and go into your graveyard. You use her -2, taking two loyalty counters off Liliana Vess and putting her into the graveyard, then searching your library for a card, shuffling your library and putting that card on top. You then have a Disentomb in your hand, however that would not return Liliana Vess from your graveyard to your hand, as she is not a creature. A card like Regrowth however, would.
Tips for using Planeswalkers
When you're building your deck make sure it fits your themes and colors. For example, you wouldn't put Liliana Vess in a white and green life gain deck, however Ajani, Mentor of Heroes would fit perfectly.
Learn how to use all its abilities, with all the angles. Sorin Markov is a prime example of this. His -3 can be used to cut down a player with a high life total and bring them into burn spell/creature damage range, or it can be used to save your life in a pinch.
Combos combos combos. Planeswalkers are powerful cards. A Planeswalker in the right deck is game winning. For example, a burn deck with Chandra, the Firebrand has an edge. A burn deck with Chandra, the Firebrand, Mirari, Lava Axe and Quest for Pure Flame can one shot somebody with relative ease. (In case you didn't catch that, build up Quest for Pure Flame with Chandra, the Firebrand ect, then cast Lava Axe copy with Chandra, the Firebrand and Mirari and activate Quest for Pure Flame. 30 damage, one turn. You're welcome.*)
Survival. Keeping Planeswalkers alive can be hard. Especially if your opponent knows what's coming. Try to keep creatures ready to block before you cast your Planeswalker and try to make sure you have some instants in your hand just in case. Also note that a Planeswalker can keep you alive by distracting your opponents from your life total.