Ogni episodio che ha visto Mario come protagonista ha sempre frequentato il solito topos narrativo, quello dell'eroe che salva la principessa dalle grinfie del cattivo di turno. Per quanto scontata e priva di sofisticati intrecci, un'impostazione del genere ha saputo sin dalle origini intrattenere i giocatori d'ogni età, senza mai tediarli. L'originalità con cui ogni episodio della saga ha rivisitato un luogo comune è mirabile, se si considera che l'idraulico è alle prese col ratto di Peach dal 1985: la fragilità del canovaccio è stata sempre compensata dall'eccentricità dei personaggi e dalla stravaganza delle ambientazioni.
Anche quest'ultimo capitolo non è da meno, e ripropone la solita trama inserendola però in una cornice inedita, che conferisce all'intera sceneggiatura una connotazione ancora più fiabesca.

Mario, pronto per i festeggiamenti, si incammina per raggiungere Peach ma, sulla via che conduce al festival delle stelle, è sorpreso dalla flotta di navi volanti di Bowser, che attaccano il Regno dei Toad per portar via nello spazio oscuro l'intero castello, con la Superstella e la principessa che vi soggiornano. All'eroe, ricacciato nel vuoto cosmico dal perfido Kamek ed intercettato dagli Sfavillotti, non resta che mettersi sulle tracce di King Koopa, assistito dall'eterea Rosalinda e dai suoi piccoli aiutanti.

Super Mario Galaxy propone una nuova concezione del platform game, anzitutto per il modo in cui è concepito il level design: Mario deve esplorare un gran numero di galassie, la maggior parte delle quali è composta da più pianeti, e recuperare le Superstelle. Ogni galassia rappresenta un microcosmo unico, perché risponde a schemi propri: alcune infatti sono composte da più livelli, uno per ogni Superstella, altre invece (con una sola ricompensa finale) presentano uno scenario impostato secondo le dinamiche di un racing o di un puzzle game. Se è vero che il puzzle solving contraddistingue qualche stage, il ritmo di progressione avanza costantemente, cosicchè tali "interruzioni" sono volute all'interno dell'economia del gioco e centrano l'obiettivo di diversificare l'esperienza, senza che essa risulti mai frammentaria. Del resto Super Mario Galaxy lavora proprio sulla base del platform game classico, con pochissime contaminazioni, per reinventarla e sconvolgerla.
Così, sulla base di una struttura a "comparti stagni" (che sulle prime può sembrare quasi "episodica"), l'idraulico inizia i suoi viaggi dall'Osservatorio Cometa, che è la “base operativa” dalla quale spicca il volo per raggiungere i mondi sbloccati e visualizzabili nei planetari. Giunto sull'ultimo pianeta di ogni galassia recupera la Superstella, oppure affronta un boss finale. I pianeti hanno una geografia variabile, per dimensione e conformazione; molti possono essere esplorati solo in superficie, taluni nascondono scenari interni (per lo più quadri bonus per raccogliere power up) cui è possibile accedere attraverso i tubi. Sovente, inoltre, i corpi celesti dalla forma schiacciata celano oltre l'equatore un'ambientazione antitetica rispetto a quella dell'altro emisfero, sicché a lussureggianti prati in fiore si contrappongono tetri alberi e costruzioni spettrali. Insomma, alla base dell'esperienza di Super Mario Galaxy si trova la piacevolezza di un level design d'alta scuola, fuori da ogni schema, e la "sfavillante" creatività delle situazioni di gioco, capaci di emozionare gli utenti senza mai fermarsi, durante tutto il corso dell'avventura. Ed è proprio in virtù di questa varietà concettuale, formale, visiva, che Galaxy resta impresso a fuoco nei cuori e sulle retine di chi lo ammira. Prova lampante di un lavoro incredibilmente ispirato, oltre ai molti inserti a tema (piccoli minigiochi corsistici, ad esempio), sono i combattimenti con i boss, a volte celati in livelli bonus o imprevedibilmente disseminati per le galassie. Molto diversi tra loro, risultano tutti affascinanti e ben strutturati, complice anche una caratterizzazione dei nemici che li rende persino simpatici.
Come ogni platform che si rispetti, anche Mario Galaxy nasconde, con buona pace degli hardcore gamer, tanti livelli bonus che possono essere visitati raccogliendo gli oggetti necessari. Tuttavia, generalmente nelle fasi di gioco e persino nel posizionamento dei segreti, il titolo si attesta su livelli di difficoltà tutt'altro che elevati. Riesce certo ad impegnare l'utente con una complessità strutturale sopra le righe, ma si lascia al contempo portare a termine con estrema leggerezza, dimostrandosi mediamente più facile rispetto a Super Mario 64.
Il sistema dei power up introduce interessanti novità che contribuiscono a fare del titolo un “unicum”: si raccolgono le Astroschegge, sparse in grande quantità per i livelli, che possono essere accumulate per ottenere una vita extra oppure “spese” per lanciarle contro i nemici o darle in pasto agli Sfavillotti, ottenendo varie ricompense utili al prosieguo dell'avventura o a giocare i livelli segreti. L'ultima testimonianza della capacità della serie di sapersi rinnovare, prestando fede alla consolidata tradizione, è fornita dall'inserimento di nuovi nemici e dal meno banale ingresso di quei funghi che conferiscono al protagonista inedite capacità (Mario spettro è esilarante) o ne rivisitano di già note, come la capacità di volare trasformandosi in ape anziché in procione. In verità, dispiace che le trasformazioni siano poco sfruttate, anche per il positivo feedback visivo che hanno; tuttavia l'uso di alcune (come Mario Fuoco) risulta troppo macchinoso, e questo ne determina forse l'esigua presenza.