Mario
NES (1985 - 1996, 11yrs): SMB (1985), SMB2 (1986), SMB3 (1990)
SNES (1991 - 1999, 8yrs): SMW (1991), SMW2 (1996)
N64 (1996 - 2002, 6yrs): M64 (1996)
GC (2001 - 2007, 6yrs): SMS (2002)
Wii (2006 - ??): SMG (2007)
As we can see, they only put out a *main* series Mario game every 4-5 yrs. It takes awhile to make a great game and they will not put out a main series mario game that is not considered great to them. To have more than one on the same console the life of the console must last at least 8-10 years IMO. So IF the Wii is going to appear lasts until 2016 or so, as it probably will, it might see a galaxy 2 in like 2011 or they might hold off for another Mario game to launch with WiiHD in 2012.
Zelda
NES (1985 - 1996, 11yrs): LoZ (1987), Z2:AoL (1988)
SNES (1991 - 1999, 8yrs): LoZ:LttP (1992)
N64 (1996 - 2002, 6yrs): LoZ:OT (1998), LoZ:MM (2000)
GC (2001 - 2007, 6yrs): LoZ:WW (2002), LoZ:TP (2006)
Wii (2006 - ??): LoZ:TP (2006)
Zelda is slightly different. I has a new game every 2-3 yrs on average. Given that TP was actually a GC game that was altered in the last phase to be on Wii as well. Plus, it was delayed by about a year, so it shoul dhave been out in 2005 technically. I would bet we see the next Zelda for release in Winter 2009 or 2010 at the latest.
Basically with Nintendo's flagship titles we can expect one every 4 years or so depending on the lifespan of that particular console, mostly. Due to the short lives of that last two consoles from launches only one per term was really doable. Since Wii is leading the gen, we might expect 2 of each for the Wii.
I also expect an iteration of probably all of Nintendo big IP's by 2010.