On a beau s'y attendre et se dire que cette fois on ne nous y prendra pas, on se laisse toujours prendre au piège. Au vu des histoires alambiquées des précédents opus, le scénario de Paper Mario 2 ne pouvait qu'être une épaisse bouillie d'ingrédients sans queue ni tête. Le résultat va encore au-delà puisque, l'univers du plombier s'enrichissant à chaque nouvel épisode, on nous sert ici un florilège de personnages hétéroclites et de situations toutes plus improbables les unes que les autres. Le canevas scénaristique qui soutient l'ensemble des péripéties du jeu se base sur une nouvelle imprudence commise par la princesse Peach, décidément fort ingénue. En visite dans une ville de truands, la princesse reçoit, des mains d'un mystérieux personnage encapuchonné, un coffre contenant une carte au trésor. Dès lors, plus aucune trace de la jeune fille. Mario et Luigi n'ont pour seul indice qu'une lettre qu'elle leur a envoyé afin de les mettre au courant de sa nouvelle acquisition, la carte, qui passe alors aux mains des deux frères. Trop poltron pour partir à l'aventure, Luigi laisse alors son frère partir seul à la recherche de la princesse. Une quête qui le guidera sur les traces de dangereux ennemis mais aussi d'alliés qui l'aideront à comprendre la signification de la carte et du trésor qu'elle indique, un trésor lié aux sept pierres d'étoiles que tout le monde désire et qui doivent permettre d'ouvrir la porte millénaire. La recherche de chacune de ces pierres donne lieu à un nouveau chapitre qui fait intervenir de nouveaux décors, de nouveaux protagonistes et une nouvelle intrigue.