Remember Super Mario RPG? It was basically the swansong of the SNES, and though sales for it were fairly poor (Since people had moved on to new consoles and all), the games managed to build up quite a fanbase, and is, nowadays, one of the most popular Mario games ever made, despite not being released in half the world (Europe/Australia).
It was no wonder then, that in 1997, only a year after SMRPG was released, Nintendo announced that they were making another Mario RPG game. Tentatively titled "Super Mario RPG 2", Paper Mario looked completely different from it's spiritual predecessor: Characters and environments all looked 2D, and when things turned around, you could see that they were paper-thin! The game was finally released in 2001 for most regions (Those lucky Japanese got it in 2000!).
Though the game is a departure from SMRPG in many ways, it still proved to be a success. Gameplay is still very similar, with the objective being to find 7 stars around the world in order to restore peace. The battle system is changed slightly - You do not have a team of three characters you can swap around with two more. Instead, your team consist of Mario and one partner. Partners are usually weak HP-wise, but have some very nice special moves that benefit you greatly. One, for instance, can temporarily make Mario invincible to enemy attacks! In-battle, your partner will hang around behind Mario for safety in order to pull off moves of his own. Partners are invincible, but if they get hit, they will not be able to move for a number of turns. You can also block moves by pressing a button at the right time, or dish out more damage yourself by doing the same. Located in various spots around the world are badges - You can put these on Mario to enhance attack power, make him impervious to spiky things and more. When you level up after getting 100 "Star Points" by defeating enemies, you can raise HP (Health Points), FP (Flower Power for special moves) or BP (Badge Points, to equip more badges).
You progress through the game in a fairly linear manner, similar to SMRPG. Locations are varied, with Toad Town acting as the central hub, with paths branching off to locations like a jungle, a haunted forest, a desert, a snowy mountain and more. There are lots of sidequests and secrets for you to discover, which will aid you quite a bit when done.
The game is divided into 8 chapters, each one ramping up in difficulty, until the final one, which is a massive multi-hour trek through Bowser's Castle, filled with dangerous enemies. Each chapter has it's own boss, which are usually pretty hard compared to their lackeys.
The game has very witty dialogue which should make you chuckle at least a few times. It's all well written and adds some life to the Mario world, which is usually devoid of much text.
The soundtrack is absolutely brilliant - Yuka Tsujiyoko, of Fire Emblem fame, composed it all. The songs are very varied and fit the areas they're in well. Each chapter boss has it's own special battle music, which is even cooler than the other music.
Paper Mario was, much like Super Mario RPG was to the SNES, the swansong of the N64. It was followed by a sequel, Paper Mario: The Thousand-Year Door, in 2004. It's still a frequent debate which of the two is better, though I would have to go with the sequel. Still, the original Paper Mario is also brilliant! Since the Wii can play GameCube games, you can just buy Paper Mario on VC and hunt down a copy of the sequel if you don't already own it. Any self-respecting Nintendo fan should play at least one of them.