Même si cela n'a jamais été le point fort de la saga, commençons par un petit point sur l'histoire. Une fois de plus, le petit plombier en rouge et bleu se rend auprès de sa dulcinée. Cette fois-ci, et selon la lettre de sa belle, il serait question de « regarder la pluie d'étoiles filantes qui n'arrive que tout les cent ans en dégustant des petits gâteaux ». Toujours sur sa faim, et espérant sans doute un peu plus de la part de la délicieuse Peach, Mario parcourt la lande, en profitant au passage pour réviser ses plus beaux mouvements (une sorte de tutorial, vous l'aurez compris). Le coeur sur la main, il en profite pour recueillir un Luma blanc qui trouve bien vite refuge sous sa casquette. Arrivé au château, horreur, un Bowser gigantesque sème chaos et désolation, emprisonnant les Lumas dans des cristaux, faisant pleuvoir des météorites et surtout, privant Mario de la compagnie de sa promise. Ayant assimilé le pouvoir des étoiles, le vil saurien se carapate vite fait, rêvant de fonder un empire galactique à sa mesure, et rêvant secrètement que Peach lui fasse des biscuits grands comme des galaxies... Ni une ni deux, et sans doute un peu énervé par le rapt de sa princesse, le moustachu décide donc de s'envoyer en l'air avec les Lumas rescapés et leur nef spatiale, un planétoïde remodelé à l'effigie du plombier qui marche aux étoiles. Vous voilà donc lancé dans une énième session de collecte d'étoiles ainsi que dans la poursuite effrénée de votre rival de toujours, qui vous mènera soyez en sur, jusqu'au confins de l'univers.

Le premier changement notable qu'apporte cette deuxième aventure galactique de Mario intervient dès la séquence d'introduction passée. L'observatoire du premier, qui servait de hub gigantesque et distribuait au fil du temps l'accès au différents monde, laisse ici la place à une carte des plus traditionnelle, à l'image du travail qui a été effectué sur New Super Mario Bros Wii. Chaque « monde » comporte une entrée et une sortie unique, et il vous faudra trouver votre chemin, et récolter suffisamment d'étoiles au passage pour accéder au monde suivant. Bien évidemment, la fin de chaque monde est sanctionnée par la sempiternelle épreuve du château, qui comme à son habitude est constitué de force lave, boules de feu et autres barres de flammes tournoyantes. Le tout se soldant immanquablement par un affrontement dantesque contre un boss vous dominant de sa taille. Une fois cette menace éliminée, vous obtiendrez une grande étoile donnant naissance à un nouveau monde, jusqu'à l'affrontement final contre Bowser. Chacun des six niveaux que compte ce Mario Galaxy 2 connaît, à l'exclusion de son tracé interne, une structure commune. Même nombre de sous-niveaux, ou galaxies comme ils sont nommés ici, nombre d'étoiles à moissonner équivalent, présence d'un goinfre Luma ouvrant un nouveau passage, etc. Cette répétition de la structure se retrouve même au sein des galaxies, qui comportent toutes un nombre précis d'étoiles à trouver, ainsi qu'une pièce comète. Ces dernières servent d'ailleurs à faire apparaître les Comètes Farceuse, qui viennent se coller à un niveau déjà traversé, et qui, en plus d'apporter une étoile supplémentaire au dit niveau, corsent la difficulté en proposant des challenges qui raviront à coup sur les accros de la performance. Niveau en temps limité, collecte de pièces violettes, affrontement des anciens boss avec une seule unité de vie et autre joyeuseté du même acabit seront au programme de ces session ou l'habileté prime.

Entre chaque niveau, et après obtention d'une étoile, le père Mario retournera sur son vaisseau et pourra profiter des améliorations apportées par le niveau qu'il vient de traverser. Car cette base mobile évolue au fil du temps, jusqu'à constituer une petite arche de Noé rappelant les épreuves ainsi traversées. De nombreux animaux croisés de ci de là viendront ainsi prodiguer divers conseils de gameplay, tandis que les Toads proposeront divers services, comme une banque de fragments d'étoiles (dont le compte est commun aux trois sauvegardes) et une poste, délivrant de temps à autres des lettres de protagonistes rencontré précédemment, vous informant de l'apparition d'un nouveau challenge, ou vous prodiguant des encouragements, avec à la clefs quelques vies supplémentaires bienvenues. Moins fourni que l'observatoire, le vaisseau permet tout de même de souffler entre deux niveaux en proposant de menues activités.