What are you using it for?
Digital alone, it probably wouldn't mind 10% ripple. That's what I would guess. More than that and I have to wonder if you'll start seeing flipped bits and random crashes. Will depend on how spiky it is (which will, in turn, depend on the ESR/ESL of the filter caps, and if your layout contributes any ESL). This assumes you still have local bypass, since every time the chip changes state (let alone an IO pin), a big gulp of current is required.
If you're expecting to use anything analog (ADC, comparator), you'll want it better than that, especially where 'the rubber meets the road' (extra filtering on AVCC!).
I think I would be surprised if less than... uh, maybe 0.1% ripple or so, would be necessary? Just because, the onboard analog stuff is so bad (what is it, 4-10 LSBs on a mere 10 bit ADC?) that, if you need more than 8 bits or so, you simply don't use the onboard stuff at all. The external stuff, of course, needs to be filtered as well as it requires.
A related theme is this:
There's a guy on a newsgroup who claims he reduces the bypass capacitor population on every new design he makes -- this is mostly regarding FPGAs. His stuff always has internal ground planes, so the power supply impedances are low to begin with. I don't know if he's reached the point yet, but others have claimed boards with few or no small local bypass caps at all. This is possible (though not necessarily achieved, mind you!) because internal layers provide the capacitance for high frequencies, and bulk capacitors for low. A two-layer board won't have this luxury, but the number of bypasses still need not be extreme.
What matter more is this: rather than shrugging off the power supply, the astute engineer should look at it as an impedance network, just as everything else is; the goal in this case* is to provide the lowest, most stable impedance, at all frequencies, to any point in the circuit. Now, rather than being a series of traces or planes, the power supply rail itself becomes an RLC filter network, and one can draw at least partial conclusions from its local design.
*Except when it's not. Switching supplies are a good example, but that's a post for another day.
And with that in mind, even without performing a complete analysis of the full system, one can gather some ideas: an IC at the end of a long, narrow trace will see a high inductance; a bypass capacitor will certainly be required there. But the capacitance will resonate with the inductance. And that resonance corresponds to some impedance. Contrary to some conventions, low ESR is not always the ideal: rather, one must strive for a damped network, which sometimes means increasing ESR, to dampen those LC resonances.
Tim