Damaging a linear regulator applying a voltage to the output
You need to avoid backfeeding the regulator. This is done by diode ORing your two power sources (regulator and bus power). Note that [depending on your budget and requirements] this can be done with Schottky diodes or with ideal [IC, MOSFET-based] diodes, e.g. these.

The protection that Dwayne describes is useful when you cut the battery power to regulator (so its output may temporarily see higher voltage than its input), but is not a substitute for diode ORing when using multiple power sources that all have power at the same time.

Regarding heatsink: how much power are you drawing? At idle the Atmega328 shouldn't use more that 100mW so if you find yourself needing a heatsink at idle, something is probably wired wrong. That means 20mA at the most through the reg at idle. Times 4V (=9-5) it's about the same power dissipated in the regulator. Actually, which package of uA78M05 are you using? In the TO-220 you shouldn't be able to feel anything at this power, but with the smaller SOT223 package you might feet a small warm spot.