Summary: YOU NEED A HEATSINK NOW !!!!! :-)
[and having a series resistor as well wouldn't hurt :-) ]
Well asked question Your question is asked well - much better than usual.
The circuit diagram and references are appreciated.
This makes it much easier to give a good answer first time.
Hopefully this is one ... :-)
It makes sense (alas): The behavior is entirely expected.
You are thermally overloading the regulator.
You need to add a heat sink if you want to use it in this manner.
You would benefit greatly from a proper understanding of what is happening.
Power = Volts x Current.
For a linear regulator Power total = Power in load + Power in regulator.
Regulator Vdrop = Vin - Vload
Here Vdrop in regulator = 24-5 = 19V.
Here Power in = 24V x Iload
Power in load = 5V x Iload
Power in regulator = (24V-5V) x Iload.
For 100 mA of load current the regulator will dissipate
Vdrop x Iload (24-5) x 0.1 A = 19 x 0.1 = 1.9 Watt.
How Hot?: Page 2 of the data sheet says that the thermal resistance from junction to ambient (= air) is 50 degrees C per Watt. This means that for every Watt you dissipate you get 50 degrees C rise. At 100 mA you would have about 2 Watts disspation or about 2 x 50 = 100C rise. Water would boil happily on the IC.
The hottest most people can hold onto long term is 55C. Yours is hotter than that. You didn't mention it boiling water (wet finger sizzle test). Let's assume you have ~~ 80C case temperature. Let's assume 20C air temperature (because its easy - a few degrees either way makes little difference.
Trise = Tcase-Tambient = 80-20 = 60°C.
Dissipation = Trise/Rth = 60/50 ~= 1.2 Watt.
At 19v drop 1.2 W = 1.2/19 A = 0.0632 A or about 60 mA.
ie if you are drawing about 50 mA you will get a case temperature of 70°C - 80°C degrees range.
You need a heatsink.
Fixing It: The data sheet page 2 says Rthj-case = thermal resistance from junction to case is 5C/W = 10% of junction to air.
If you use a say 10 C/W heatsink then total Rth will be R_jc + Rc_amb (add junction to case to case to air).
= 5+10 = 15°C/Watt.
For 50 mA you will get 0.050A x 19V = 0.95W or a rise of 15°C/Watt x 0.95 ~= 14°C rise.
Even with say 20°C rise and a 25V ambient you will get 20+25 = 45°C heatsink temperature.
The heatsink will be hot but you will be able to hold it without (too much) pain.
Beating the heat:
As above, heat dissipation in a linear regulator in this situation is 1.9 Watt per 100 mA or 19 Watt at 1A. That's a lot of heat. At 1A, to keep temperature under the temperature of boiling water(100°C) when ambient temperature was 25C you'd need an overall thermal resistance of no more than (100°C-25°C)/19 Watt = 3.9 C/W. As the junction to case Rthjc is already greater than 3.9 at 5 C/W you cannot keep the junction under 100°C in these conditions. Junction to case alone at 19V and 1A will add 19V x 1A x 5 C/W = 95°C rise. While the IC is rated to allow temperatures as high as 150°C, this is not good for reliability and should be avoided if at all possible. Just as an exercise, to JUST get it under 150°C in the above case the external heatsink would need to be (150-95)C/19W = 2.9 C/W. That's attainable but is a larger heatsink than you'd hope to use. An alternative is to reduce the energy dissipated and thus the temperature rise.
The ways of reducing heat dissipation in the regulator are:
(1) Use a switching regulator such as the NatSemi simple switchers series. A performance switching regulator with even only 70% efficiency will reduce the heat dissipation dramatically as only 2 Watt is dissipated in the regulator!.
ie Energy in = 7.1 Watts. Energy out = 70% = 5 Watts. Current at 5 Watts at 5V = 1A.
Another option is a premade drop-in replacement for a 3 terminal regulator.
The following image and link are from the part referred to in a comment by Jay Kominek. OKI-78SR 1.5A, 5V drop in switching regulator replacement for an LM7805. 7V - 36V in.

At 36 Volts in, 5V out, 1.5A efficiency is 80%. As Pout = 5V x 1.5A = 7.5W = 80%, the power dissipated in the regulator is 20%/80% x 7.5W = 1.9 Watts. Very tolerable. No heatsink requied and can provide 1.5A out at 85 degrees C. [[Errata: Just noticed the curve below is at 3.3V. The 5V part manages 85% at 1.5A so is better than the above.]]

(2) Reduce the voltage
(3) Reduce the current
(4) Dissipate some energy external to the regulator.
Option 1 is the best technically. If this is not acceptable and if 2 & 3 are fixed then option 4 is needed.
The easiest and (probably best) external dissipation system is a resistor. A series power resistor which drops from 24V to a voltage that the regulator will accept at max current will do the job well. Note that you will want a filter capacitor at the input to the regulator due to the resistance making the supply high impedance. Say about 0.33uF, more won't hurt. A 1 uF ceramic should do. Even a larger cap such as a 10 uF to 100 uF aluminum electrolytic should be good.
Assume Vin = 24 V. Vregulator in min = 8V (headroom / dropout. Check data sheet. Selected reg says 8V at <1A.) Iin = 1 A.
Required drop at 1A = 24 - 8 = 16V. Say 15V to be "safe".
R = V/I = 15/1 = 15 ohms.
Power = I2*R = 1 x 15 = 15 Watts.
A 20 Watt resistor would be marginal.
A 25W + resistor would be better.
Here's a 25W 15R resistor priced at $3.30/1 in stock lead free with datasheet here. Note that this also needs a heat sink!!! You CAN buy free air rated resistors up to 100's of Watts. What you use is your choice but this would work well. Note that it is rated at 25 Watt commercial or 20 Watt military so at 15W it is "doing well". Another option is a suitable length of properly rated resistance wire mounted appropriately. Odds are a resistor manufacturer already does this better than you do.
With this arrangement:
Total power = 24W
Resistor power = 15 Watt
Load power = 5 Watt
Regulator power = 3 Watt
Regulator junction rise will be 5 C/W x 3 = 15°C above case. You will need to provide a heatsink to keep regulator and heatsink happy but that is now "just a matter of engineering".
Heastsink examples:
21 degrees C (or K) per Watt

7.8 C/W

Digikey - many heatsink examples including this 5.3 C/W heatsink

2.5 C/W

0.48 C/W!!!
119mm wide x 300mm long x 65 mm tall.
1 foot long x 4.7" wide x 2.6" tall

Good article on heatsink selection
Forced convection heatsing thermal resistance
Reducing linear regulator dissipation with a series input resistor:
As noted above, using a series resistor to drop voltage prior to a linear regulator can greatly reduce dissipation in the regulator.While cooling a regulator usually requires heats inks, air-cooled resistors can be obtained cheaply that are able to dissipate 10 or more Watts without needing a heatsink. It is not usually a good idea to solve high input voltage problems in this manner but it can have its place.
In the example below an LM317 5V output 1A supply operated from 12V. Adding a resistor can more than halve the power dissipation in the LM317 under worst case conditions by adding a cheap air cooled wire mounted series input resistor.
The LM317 needs 2 to 2.5V headroom at lower currents or say 2.75V under extreme load and temperature conditions. (See Fig 3 in the datasheet, - copied below).
LM317 headroom or dropout voltage

Rin has to be sized such that it does not drop excessive voltage when V_12V is at its. minimum, Vdropout is worst case for the conditions and the series diode drop and output voltage are allowed for.
Voltage across resistor must always be less than =
So Rin <= (v_12 - Vd - 2.75 - 5)/Imax.
For 12V minimum Vin, and say 0.8V diode drop and say 1 amp out that's
(12-0.8-2.75-5)/1
= 3.45/1
= 3R45
= say 3R3.
Power in R = I^2R = 3.3W so a 5W part would be marginally acceptable and 10W would be better.
Dissipation in the LM317 falls from > 6 Watt to < 3 Watt.
An excellent example of a suitable wire lead mounted aircooled resistor would be a member of this nicely specified Yageo family of wirewound resistors with members rated from 2W to 40W air cooled. A 10 Watt units is in stock at Digikey at $US0.63/1.
Resistor ambient temperature ratings and temperature rise:
Nice to have are these two graphs from the datasheet above which allow real world results to be estimated.
The left hand graph shows that a 10 Watt resistor operated at 3W3 = 33% of its rate Wattage has an allowable ambient temperature of upto 150 C (actually about 180C if you plot the operating point in the graph but the manufacturer says 150 C max is allowed.
The second graph shows that temperature rise for a 10W resistor operated at 3W3 will be about 100C above ambient. A 5W resistor from the same family would be operating at 66% of rating and have a temperature rise of 140C above ambient. (A 40W would have about 75C rise but 2 x 10W = under 50C and 10 x 2W only about 25C !!!.
The decreasing temperature rise with an increasing number of resistors with the same combined Wattage rating in each case is presumably related to "Square cubed law" action as there is less cooling surface area per volume as size increases.

http://www.yageo.com/documents/recent/Leaded-R_SQP-NSP_2011.pdf