マリオはクッパにさらわれたピーチ姫を助けようとしますが、その強大な力で宇宙に放り出されてしまいました。
ピーチ姫がいる遠い銀河へ行くためには、ロゼッタやチコたちが住む ほうき星の天文台 の力が必要です。
しかし、ほうき星の天文台 を動かすための力である 「グランドスター」 や 「パワースター」 が、クッパ軍団に奪われてしまいました。
マリオは ほうき星の天文台 の力を取り戻すため、宇宙のさまざまな銀河（ギャラクシー）を冒険します。

この世界には試練の番人と呼ばれる緑色のチコが3人存在しますが、クッパ軍団に奪われたために緑のパワースターへと姿を変えています。
ギャラクシーのどこかにある3つの緑のパワースターを手に入れると、試練の銀河という3つのギャラクシーに行けるようになります。
試練の銀河についてはこちらを参照。

パワースターが13個以上になるといたずらコメットが出現するようになります。
いたずらコメットが飛来したギャラクシーでは、コメットの種類によって様々なステージに変わってしまいますが、クリアするとパワースターが手に入ります。

コメット飛来中のギャラクシーでは強制的にコメットステージしかプレイできなくなりますが、天文台のテラス近くにいるコメットチコにスターピースを食べさせてドーン！してもらうと別のギャラクシーへ移動させることができます。
また、1度クリアしたコメットステージは、それ以降好きなときにプレイできるようになります。

いたずらコメットが出現するギャラクシーは、シナリオのクリア時、またはコメットチコにドーンしてもらった後にランダムに選ばれるようです。
同時に複数のギャラクシーに飛来することもあります。

制限時間内にパワースターを手に入れるとクリア。

分身と競争し、相手より先にパワースターを手に入れるとクリア。

ライフ1の状態でボスを倒し、パワースターを手に入れるとクリア。

敵や仕掛けの動くスピードが通常より早いステージでパワースターを手に入れるとクリア。

パープルコインを100枚集めるとパワースターが出現し、手に入れるとクリア。
100枚ちょうどをすべて集めたり、150枚中100枚を手に入れるステージなどがあり、また制限時間つきのステージもあります。
※ パープルコメットはエンディングを見たあとに追加されるステージです。

各メインギャラクシーには、パープルコインを100枚集めると隠しパワースターが手に入るステージがあります。
このステージをプレイするには、1度ストーリーをクリアする必要があります。
エンディングを見たあとにセーブ画面が出るので、セーブしたらもう1度そのセーブデータを再開しましょう。

1度ストーリーをクリアすると第8章と終章が追加されます。
エンディングを見たあとにセーブ画面が出るので、セーブしたらもう1度そのセーブデータを再開しましょう。

パワースターは全部で120個あります。
クリア前までで104個、クリアしたときのラストステージ（クッパギャラクシープラント）で1個、そしてクリア後にプレイできるステージで15個です。
これら120個をすべて集めて再びラストステージをクリアすると、スタッフロールのあとに隠しエンディングが挿入されます。
また、隠しキャラのルイージ（スーパールイージギャラクシー）でプレイできるようになります。

ルイージでプレイするには、セーブデータの選択画面で右上にあるマリオとルイージのボタンを押して入れ替えます。

ルイージはマリオよりもジャンプ力はあるけれど滑りやすいという特徴があります。
しかし、ジャンプ力があるがゆえに、マリオではできないショートカットも多々あります。

ルイージでもパワースター120個をすべて集めてからラストステージ（クッパギャラクシープラント）をクリアすると、スタッフロール後にグランドフィナーレギャラクシーが出現します。
マリオとルイージでそれぞれ行くことができ、クリアするとそれぞれ121個目の最後のパワースターが手に入ります。（合わせて242枚）