More anon if needed.

Your calculations are essentially correct. 

Don't forget that there is an internal 5 C/W Rjc to allow for. 

For limiting case assume junction max allowable is 125C and that internal thermal limiting will occur at that point.

To reduce power dissipation in IC for low Vout use a series resistor. 

R <= (Vin - Vo_max_with_resistor - 1.5 ) x Imax.

eg For Vout max with a given resistor of say 8V and with 26V in and with I out max with this resistor of 600 mA -

- R <= (26-8-2)/0.6 <= 26.666 ohms. Say 27 ohms

At 0.6A it will drop 0.6 x 27 =+ 16 V.  
 Vin_reg = 26-16 = 10V.  
 This gives the regulator 2V headroom.  

[LM317 datasheet](http://www.fairchildsemi.com/ds/LM/LM317.pdf) says headroom at 600 mA, warm ~= 1.8V (fig 3) so that's just marginal.

Resistor will drop V^2/R = (26-10)^2/27 = 9.5 Watt.

Regulator will drop (10-5) x .6 = 3 Watt.

It's time you got a switching power supply :-).

For interest, under these conditions the internal 5 C/W Rjc will drop 3 x 5 = 15C.  
 For junction JUST at 125C Tc = 125 - 15 = 110C.  
 Sizzles with wet finger. 
 Tca = (110-25) = 85C  
 Heatink needed = 85/3 ~= 25 C/W.

ie a modest heatsink will suffice if you don't wind boiling water temperatures on the case and heat sink. 
 The resistor will be hot :-).