Traditionally underclocking does give a reduction in power consumption, due to keeping the core cooler and its resistance down. Another great way to reduce power use and TDP is to undervolt the processor. This is an option that is available on good BIOSes. I cannot emphasise enough how careful you must be with this: like overclocking, undervolting can cause silent computation errors, which are bad news for everyone, so don't forget to check that your processor is running well before dropping the voltage further. A good Google search should provide some information about undervolting. Also note that undervolting will cause a performance reduction, like underclocking will.
Power usage reductions can be gained in other areas as well. Removing unnecessary components, particularly discrete graphics chips, can be a great help: if possible, run the box headless. It seems you want to use the P4, so it's unlikely you'll do this, but newer chips are more power efficient, and for a NAS you could potentially drop all the way to an Atom chip for power savings. A huge improvement in power efficiency can be obtained with a newer high-efficiency PSUs. These don't always come cheap, but the cheap PSUs can have pretty poor efficiencies, which will drive your energy bill up. Finally, as a corollary to my point about core temperature above, a well cooled system will tend to run more efficiently, but the improvements are harder to notice.
As a personal recommendation, though, if you can buy and mount a quiet CPU fan, do it. Having a NAS whining away in the background 24/7 can set your teeth on edge. Good luck with the conversion though!