They say you should buy a scope with 5x the bandwidth of the highest frequency you expect to encounter; so in theory, let's say you were working with the ATMega328, that would be 100 MHz of bandwidth (ie, 20 MHz clock crystal multiplied by 5).
100 MHz scopes aren't cheap, especially purchased new. I can't remember the exact reasoning behind that multiplier of 5, but from what I do remember, it was sound reasoning and made sense. I don't have any reason to doubt it, but you have to keep in mind what you are planning on doing. If you expect to be regularly probing frequencies at or near the base clock frequency that you know for a particular microcontroller you are using, then keep it in mind. However, think about what you are planning on using the scope for, then calculate the bandwidth you need based on that.
A 40 MHz scope would allow you to reliably scope out 8 MHz (and lower) signals; for most hobbyist purposes, this is likely more than enough. It doesn't mean you can't scope higher frequencies, though...