I have a rev A MBA. Early on, when these core shutdown problems started to crop up, I did some tests and found that my machine experienced core shutdowns under artificial loads (double "yes >/dev/null" processes). Didn't really have any problems with the machine outside that.
However, I did end up replacing the thermal paste and purchased a coolbook license to see if I could solve the issue. To me, it made a pretty significant difference and my core shutdowns were a thing of the past.
However, after a couple of OS upgrades (running Snow Leopard on it now) Coolbook is no longer active and the CPU runs at the stock voltages. The other day, I ran some flash video and tried the "double yes" test again for some time and my CPU temp ended up in the 75-80C range without any cure shutdowns.
To be honest, I am simply not worrying about the temperatures anymore.
To answer your question though.. What Coolbook does is somewhat of a reverse-overclocking. You configure the CPU to run at a lower voltage than the fairly conservative defaults. The net effect of this is that the CPU runs cooler (I think I read somewhere that there's a quadratic relation between voltage and temperature) when you reduce the voltage. The downside is that if you reduce the voltage too much, your computer gets unstable (unable to start up, or crashes randomly).
Setting up the voltages is quite time-consuming. What you want to do is to reduce voltages step by step and make sure you test extensively after every change. For the max frequency of your CPU, it's not all that hard to find ways to test (flash videos, games, "double yes test", coolbook's cpu load setting), but I found that it's a bit tricky to test the middle frequencies over a longer period of time (apart from coolbook's own short test).
The effect of the optimization is also dependent on how you use your computer. If you're surfing (flash-free) sites mostly, or doing light office-style work your CPU will most likely be sitting at the lowest frequency possible for your machine. If so, undervolting is not going to help you at all since you can't undervolt the lowest frequency (or at least I didn't figure out a way to do that). In this case, the only way to reduce temperatures would be thermal paste replacement (or well, certain hardware hacks come to mind but these aren't really my kind of thing).
Bottom line is that undervolting using Coolbook is mostly a trial and error process, where you have to spend a fair amount of time to find the lowest voltage settings that give you a stable machine.
