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
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.
You need XP for enchanting or repairing tools on an enchantment table or an anvil.
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!
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
2: Combining Enchantments
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:
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.
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.
Would you like to answer one of these unanswered questions instead?