Starting with beta 1.8 prerelease, Minecraft players earn XP when they kill mobs!
What are the benefits of leveling up? More health? More damage? Larger inventory?
Leveling up is currently used for 2 things: Score, and enchanting.
1 orb == 1 point. This score is displayed upon death (and possibly game completion. I haven't gotten that far :P).
As you collect orbs, your experience bar fills. Everytime it gets completely full, it empties and you level up. In this screenshot, the player is level 1.
Once you have an enchantment table, you can spend your experience on enchantments. These give one of your tools a special ability, such as a chance to not take any wear each time you use it, and additional harvesting speed.
Enchantments cost 1 to 3 levels depending on the type of enchantment, but you must be a certain level to access each one. The highest tier appears to require you to be at or above level 30 to use, while still only costing 3 levels per enchantment.
One thing to note is that as of Release 1.8 enchantments also cost 1-3 pieces of Lapis Lazuli depending on the enchantment.
BEFORE RELEASE VERSION 1.8
Every enchantment has a cost paid in levels. I.e. Level 2 enchantments cost 2 levels of experience. In my screenshot above, the player can only buy level 1 enchantments, because he's only level 1. By default, you can get up to level 5 enchantments with an enchantment table. Placing bookshelves around your table will unlock higher level enchantments.
Your experience is reset when you die, although you do drop some experience orbs, which can be recovered like anything else you drop, assuming you find your death spot. The amount dropped is 7 times your level, up to 100, or enough to reach level 5.
As of 1.9-pre4, leveling up provides skill levels that you can spend on enchantments for your items.
And as of 1.9-pre2, your total experience acts as a way to keep score: one experience orb equals once point. Combined with hardcore mode (which forces a player to delete their world upon death), it introduces elements to bring Minecraft more in line with the Roguelike genre of games—including Nethack, Angband, and Dungeons of Dredmor—that generally report your score upon game completion (read: death).
In the future, Mojang has talking about how leveling up will eventually provide a way to increase skills. What that means and how it's accomplished is entirely speculatory at this point: the only thing known for sure is that gaining enough experience orbs to "level up" would award skill points that could be spent on "powering up abilities". In terms of what powering up abilities means, Notch said:
You could upgrade run speed, or like, maximum health, or uh, [inaudible]. Stuff like that.
It's unclear if this was an idea that's been replaced with enchanting or an alternative to enchanting that has yet to be implemented.
According to the behind the scenes video for the trailer (starting around 1:35) there is currently no use of experience.
However, a future release will use experience (for some currently unknown purpose). It wasn't obvious whether this would carryover, so I'd say it's 50-50.
As of Minecraft release version 1.4.2, aka the "Pretty Scary Update", Anvils were introduced, serving all sorts of different functions.
In accordance to your question, they serve two functions related to experience:
1: Repairing and Renaming Items
Unlike crafting to repair items, Anvils can use materials to repair or combine two items. Anvils can both retain enchantments and expand on them. The player can also rename any item - not just tools or armor - using this method. This costs levels proportional to what is given. Simply renaming an item will cost 5 levels for a non-tool/armor item, whereas renaming and repairing an enchanted tool/armor is substantially more. On each use, anvils have a 12% chance to be damaged. On its last use, the GUI will close and the anvil will disappear, dropping the item on the ground.
2: Combining Enchantments
Due to the lack of a level cap in creative mode, it is now possible to combine any two (or more) enchantments on two items. Owing to the anvils ability to add two enchantments together to make a better version (like two sharpness 2 swords can be combined to a sharpness 3 sword), and the lack of a enchantment number cap (a knockback and looting sword can be combined with a fire and sharpness sword to make a knockback, looting, fire, and sharpness sword). Alone, each of these attributes is useful, but when combined together, it is possible (in creative) to make a Sharpness V, Fire Aspect II, Knockback II, Looting III Diamond Sword from a whole pile of lower enchantment tier diamond swords. (Ex: 16 Sharpness I swords, 4 Fire Aspect I swords, 4 Knockback I swords, and 8 Looting I swords can be combined into a sword with the enchantments listed above.
As of Sep 10 '11, it has no use at all. That's because Beta 1.8 is Adventure Update Part I. It will have a use in Beta 1.9, Adventure Update Part II, along with NPCs and more!
You need XP for enchanting or repairing tools on an enchantment table or an anvil.