• Mario's power-ups come in the form of various "suits":  For instance, SMB3 features Hammer Bros. suits and frog suits, while Galaxy spotlights Boos and bees.
• Mario can pick up Koopa Troopa shells, carry them, and eventually throw them at foes and targets.  This was a new ability in SMB3, one that has been absent through Super Mario 64 and Super Mario Sunshine.
• Bowser arms his child(ren) with cannon-equipped airships: The seven Koopalings terrorize the skies in SMB3, while Galaxy includes Bowser Jr.'s private airship.
• Mario must navigate platforms that actually a nut and bolt contraption.  While a common sight on SMB3's airships, these platforms appear late in the game in Galaxy.
• Bowser's domain is full of concrete statues of himself.  Bowser's castle in SMB3 was full of these tributes to the king, while Galaxy's center of the universe includes more detailed renditions of the statues.
• Princess Peach (née Toadstool) sends letters to Mario to cheer him on.  Both games also feature items enclosed with these letters for Mario to use.

Now let's look at the bigger picture.  Super Mario Galaxy is the third proper 3D Super Mario game (previous installments being, as I'm sure you know, Super Mario 64 and Super Mario Sunshine).  Likewise, Super Mario Bros. 3 was the third proper 2D Super Mario game*.  Super Mario 64 laid the groundwork for what a 3D platformer would be, much like the original Super Mario set off the 2D platformer explosion. Then came a sequel that, while a solid game, was quite different than the previous installment.  The familiar setting and enemy roster were replaced by a new location and a whole crop of enemies that weren't indigenous to the Mushroom Kingdom, and while the core gameplay remained the same, a new gimmick mixed things up a little from the last installment in the series.  Sound like Super Mario Bros. 2 and Super Mario Sunshine?

I'm not so sure that these are coincidences.  I've come to firmly believe that the Galaxy design team purposely patterned mechanics and themes from Super Mario Bros. 3 into the new game.  How can I be so confident?  Consider Rosalina's final message to Mario regarding the life cycle of stars: "When stars die, they turn to dust and scatter across the cosmos. Eventually the stardust reforms to create a new star... and so the cycle of life continues.  But the cycle never repeats itself in quite the same way."

I can't wait to see the result when the time comes for Nintendo to parallel Super Mario World...

* ignoring the "Lost Levels", of course