When to use a heatsink for a voltage regulator?
Simple enough.

The part datasheet will specify thermal resistances. Looking at a LM7805 datasheet from Fairchild (just the first one to pop up in a search) thermal resistance is 5C/W junction to case, and 65C/W junction to air.

Max operating temperature is 125C. If the device is in a 25C environment, you can handle 100C rise (though some things fall off at Max Operating Temperature, typically) so about 1.5W (100C/65C/W) will be all you can dissipate without a heat sink. If your input supply is 30V, that's perhaps 60mA; if the input is 12V it's more like 214 mA; if your input is 8V, it's 500mA. (All at 25C ambient.)

Working the example the other direction, your comment indicates a 24V supply and a dissipation of 0.38W; 0.38W * 65 C/W = 24.7 C, so you can run that up to an ambient of 100.3 C without a heatsink.

EDIT: In all of the above I have evidently neglected the regulator's own current use of 5.5-6mA (at full input voltage), located a long way down the datasheet, which adds to the power load; in your 24V example this would lower your ambient safe range to about 90 C

When you add a heat sink, you will have the 5C/W junction to case (thermal resistance) plus a certain amount of thermal resistance from the case to the heatsink (influenced by thermal grease, insulators or not, etc.) and finally the heatsink's more favorable resistance to air. 

So if the interface is 2C/W and the heatsink is 10C/W, you'd have a total of 5+2+10=17C/W from junction to air with interface and heatsink.

With the 7805 having a grounded case/tab, it's easy to bolt it to the side of a metal case/chassis for some "free heatsinking" if desired. When prototyping, if using parts with thermal overload protection (which is claimed but not fleshed out in the datasheet) you can "just see if the part gets hot and shuts down" though you should run the numbers before finalizing the design, especially since prototypes often have better natural convection than a finished product.