Related questions under this topic might include:
Generally speaking these are done as vaguely exponential curves. http://kol.coldfront.net/thekolwiki/index.php/Advancement#Advancement_Requirements_Overview shows the formulas for Kingdom of Loathing, which are pretty standard for the MMO genre.
I actually cover this very topic when talking about numeric relationships in games: http://gamebalanceconcepts.wordpress.com/2010/07/14/level-2-numeric-relationships/
You can make it however you want, although typically it's on an increasing curve (so each level requires more XP than the last), because encounters/quests tend to give more XP as you progress.
The key isn't to concentrate solely on the XP-Level curve or the XP-per-encounter curve, but to compare the two of them. If the XP-Level curve increases faster than XP-per-encounter, the player will notice they are gaining levels more slowly over time, which is pretty standard for the genre. However, the danger is that if level ups get TOO few and far between in the endgame, then the player's last memory of your game will be a colossal grind, which you probably don't want either. So figure out how many encounters per level-up are acceptable in the end game, and how many encounters per level up you want in the early game, and interpolate from there.
Also, I should mention that you CAN have overlapping reward systems other than just XP/Levels. Some RPGs have job points (so you have multiple leveling/advancement systems), so that it might be awhile between (say) leveling up your Fighting skill or your Healing skill, but with enough different things leveling up you're always just a few minutes away from increasing SOMETHING. Other RPGs have random item/equipment drops, so every new encounter doesn't just give XP, but also a small chance of generating some epic loot, so you get some additional random rewards just for playing.
I'd say it's dependent, at least partially, on the type of experience you want to create for the player. Consider two examples, the first of which is a classic turn-based RPG, the second is a Gradius III-type shooter, in which you'd like the player's power to scale based on progress since his list death, not on powerups (not to say that's a good system, just an example).
In the case of the RPG, your system probably operates on the assumption that a player never loses experience. Similarly, it will probably want to act based on the assumption that it's relatively easy to gain some level of proficiency in something, but difficult to master it (like most things in the real world). In this case you might want to develop a formula (like coderanger suggested) that is exponential in some regard. Where the amount of experience required to reach the next level is somehow exponentially based on your current level. Important to consider, however the rate at which your player will be receiving experience while playing. For instance, a player killing a level 63 Fire Demon would expect to receive more experience for his kill than if he had killed a level 2 Lady Bug. So when designing your formula, be sure that you take into account your XP system. Particularly since if you do not, then killing the lady bug will be just as profitable as killing harder enemies.
Example 1 (Likely not a form you would use): XP_TO_LEVEL = ((CURRENT_LEVEL + 1) ^ SCALE) * XP_BASE
Example 2: XP_TO_LEVEL = (XP_BASE * CURRENT_LEVEL) ^ SCALE
Where XP_TO_LEVEL is the XP needed to reach the next level. CURRENT_LEVEL is the player's current level. XP_BASE is an arbitrary number to decide how much each level is "worth" in XP. SCALE is the exponent determining how fast to scale the XP needed to level. If SCALE is 1 then each level will take XP_BASE experience. If SCALE is less than 1 then each level will take less experience than the last level. If SCALE is greater than 1 then each level will take more experience than the last level.
The following table assumes a SCALE of 1.1 and an XP_BASE of 100 using example 2.
Current Level XP Needed Increase from Last Level
1 158 0
2 339 181
3 530 191
4 728 198
5 930 202
...
10 1995 218
Example 3: XP_TO_LEVEL = ((CURRENT_LEVEL * SCALE) ^ 1.5) * XP_BASE
Where SCALE is still determining how fast to scale the XP_TO_LEVEL, but it operates a little differently.
The following table assumes a SCALE of 22 and an XP_BASE of 10 using example 3.
Current Level XP Needed Increase from Last Level
1 28 0
2 80 52
3 146 66
4 226 80
5 316 90
...
10 894 130
In the case of the Gradius clone, you might take a different strategy. You may want the player to level up consistently, say about every two minutes. In addition, after a play has lost a life and consequently lost all of his gained powers, you may want to help him along by leveling him/her up faster until he reaches an appropriate level for his progress through the game. In this case your formula will likely be more linear, especially since the user doesn't get to see how much experience he's getting per kill. Something like, it takes 50 XP to reach a new level and each enemy is worth 1 XP. This works great providing you are supplying him with a relatively steady stream of enemies. But, when the player dies, he loses it all! What do you do now? Each enemy should be worth more than 1 XP to meet your goal of catching him up so that the game is fair again.
Example: XP_FROM_EACH_ENEMY = BASE_XP + (CURRENT_LEVEL - DESIRED_LEVEL) Where XP_FROM_EACH_ENEMY is how much XP an enemy would award when killed. BASE_XP is how much XP an enemy is worth by default (could vary per-enemy type). CURRENT_LEVEL is the level of the player DESIRED_LEVEL is the level you think the player should be at.
Personally I use.
C/(A x B)
Where: A= Time for an encounter/kill (average easy, normal and hard enemies) B= Exp per kill. (average easy, normal and hard enemies) C= Time spent for the player to level up.
Note: All these are relative to pace and point in the game.
I think it may be very simplistic but note that you also set the other elements. By using a simple equation you can easily adapt to changes midway.
