The reason that capacitors are placed between IC supply pin(s) and power return (ground) is usually to filter out noise produced as current pulses are sucked into the IC (sorry if I'm stating the obvious). This is mostly a consideration with digital ICs, not so much with say linear amplifiers. CMOS digital circuits, for example, generally only draw current when they switch. Thus, the supply current tends to go in pulses. These current pulses create voltage noise as they flow through the finite interconnect resistance between the power supply and the IC. Additionally, the power supply (or battery) will generally have a finite output resistance which will have a voltage drop across it as current is pulled from the power supply. And since many circuits usually share a supply, everybody sees this noise -- not a good thing for sensitive circuits.
However, with a "local" filter (decoupling) capacitor placed right at the IC supply pin, most of the current pulse will be pulled out of the local capacitor and will not need to come from all the way from the power supply. And since the pulse is brief, the total charge taken out of the cap will be small enough that the capacitor voltage will droop only a little bit--so not much current will need to come from the supply to charge it back up over each switching cycle. Upshot: noise on the supply rail is greatly reduced.
As others have suggested, the clock frequency is not so much the problem. The amplitude of the current spikes is the problem. The more transistors switching, the more current will be drawn. And since the transistors switch very quickly, the current pulses will be very brief (this is sort of what is meant when talking about edge rate or slew rate). You could imagine a situation where many many transistors switch synchronously at 10Hz and draw gigantic current spikes. So indeed, clock rate does play a large part, but not the only part.
Decoupling is primarily an issue with digital ICs, but you do generally want to use decoupling caps on the rails of say an opamp as well, since it will help filter out noise produced by other circuits.
Updated: generally the rule of thumb would be to stick a 0.1uF on each power pin. Shouldn't take up too much space. Even if the RMS current is low, the pulsed current could be higher. But if you have a noise-robust system (all digital, few components, low power, low current), it may not really matter much...