Just a little techno info on VReg heating on the common, easy to use three-terminal regulators like the LM7805 family.
A voltage regulator drops the input voltage to produce an output voltage. This voltage drop times the current draw equals the power dissipated by the VR.
So (Vin-Vout) * I = Watts of heat. This number is then used to choose a heat sink or to determine if a heat sink is not needed. In the example posted above if the circuit is drawing 500mA the VR needs to dissipate 2Watts of heat, (9v-5v)*0.5A = 2W.
If your VR is getting much hotter than expected there could be other reasons.
If you are using a Wall wart power supply check its output voltage with a DV voltage meter. Then check the ripple using an AC voltmeter (a DMM will work on 50-60Hz). Many of those cheap wall warts either have poor voltage regulation and/or poor AC filtering.
Try powering from a battery, pure DC without any ripple.
Finally, sometimes linear regulators oscillate. This is usually due to improper bypass caps on the input or output, or the leads from the regulator to the caps is too long. Check the data sheet for recommendations and add a cap very close to the regulators input or output pins.
Hope this helps