Would it be possible to add a power saving function to m0n0wall that turned the router off when the last computer to be on the network turned off or disconnected from the router. You could just set every computer you have to do a wake-on-lan to the router to wake it back up if it were in power saving mode at the time.
While I'm sure a hack would be possible, if the m0n0wall box isn't doing much CPU or hardware wise, even on a PC, I only measure about 23 watts of power usage (PIII 800 MHz, HDD, etc) at least when the power down function of the HDD kicks in. The HDD and fans tend to be the biggest power hogs, but as was said earlier, even better form factors exist to use about the same power as a kids toy.