To get more technical, you first calculate the power dissipated in the 317. This equals the voltage in minus the voltage out times the output current (Vin-Vout) x Iout = Power dissipated.
Then you buy a heatsink that can keep the temperature of the device below its maximum rating. This is typically 125C but for reliability, you usually want to keep it below 100C.
Heatsinks are rated in the thermal resistance to air in degrees C per watt. The 317 case also has a thermal resistance from junction to case, listed in the data sheet, which varies depending upon the case type. This must be added to the heatsink thermal resistance. The temperature rise is then watts dissipated times the total thermal resistance Trise = Watts x (TRsink + TRcase). Trise is added to the ambient temperature to get the junction temperature.
Note: This is for a heat sink that is in open air.
For low power you may not need a heatsink. In that case you use the 317 thermal resistance of the case to air, which is also in the data sheet.
To minimize the mounting thermal resistance it is good practice to use thermal grease between the case and heat sink (Radio Shack among others sell such grease).
Heatsinking is also discussed in the LM117/317 data sheet from National Semiconductor. (It's amazing the information that's in a data sheet. Unfortunately, few people seem to read them.)