Here are some good factoids from Iwata's interview with and Tezuka and Nakago:

• The first Super Mario and Zelda titles were made simultaneously, with the same staff.
• Spinning bars of fire were first in Zelda, but were then transferred to Mario.
• At first Zelda was only going to be a series of dungeons (no over ground world)
• SMB levels were designed on graph paper, and took a full day to get a change onto a ROM.
• World 1-1 was the last level finished.
• The grass and clouds in SMB are the same object.
• Goombas were added last.  At first it was going to be only Koopa Troopas.
• Heart pieces in Zelda came about because they wanted more items in the game.
• The P-Wing from SMB3 stands for Paratroopa (Koopa Paratroopa's wing)
• Miyamoto wanted to put Yoshi in SMB3
• They attempted to put multiplayer in SMB3, SMW, and NSMB DS.
• All the Super Guide & Hint Movies in NSMB Wii were performed by real players.

"So in that sense, you could describe New Super Mario Bros. Wii as being the first straight-ahead evolution in the horizontally-scrolling 2D platform game since Super Mario World, with which it is comparable in terms of the attention to detail and care that went into it."