edit: Oops, I calculated this for a 15V power supply. In any case, you'll need to repeat this with your own figures, so it's not a real problem.
I sense the need for a new tutorial...
The junction has a certain max temperature. Let's say that's 125C. (The datasheet says 150C, so I'm being very conservative)
But to be nice to the regulator, we want to keep it at or below 100C.
Let's also assume that we have a maximum ambient temperature of 45C
OK, that means we must limit the rise of temperature of the junction to 55C
So, what is the power dissipation? Let's assume that your input voltage is 20V. This means that (20-15) * 1 Watts are being dissipated. (5W)
Temperature rise, power, and thermal resistance follow a law similar to Ohms law. R (thermal resistance) = T (temp rise) / P (power). So the maximum thermal resistance is 55 / 5 = 11. That's 11degC/Watt. Which literally means a rise of temperature of 11 degrees for each Watt dissipated.
You sat that the thermal resistance from Junction to case is 5degC/W. The datasheet says 4, but let's go with 5.
So from our original budget of 11degC/W, we've already used 5, leaving us 6.
The device must be mounted on the heatsink, and typically you can lose between a 0.5 and 1.5 degC/W with a GOOD thermal connection (that's with thermal paste). Let's go mid-way and assume 1 degC/W -- we have 5 DegC/W left...
Now we need to choose a heatsink. Fortunately they are rated in degC/W. All we need to do is find one rated at 5degC/W or lower, right? No. The ratings given are for optimum orientation in free air, and that may not happen in practice. A good rule of thumb is to look for a heatsink with HALF the required thermal resistance. So, we're going to look for one of 2.5degC/W
Now, 2.5degC/W is going to be a pretty large heatsink. You may be happy with that, it might fit well, and not cost more than you want to pay.
But maybe it doesn't.
Let's assume that the best you can find is 4degC/W.
Let's work backwards to see what it gives us.
4DegC/W, let's assume 8. Add 1 for the thermal connection to the device, and 5 for junction to case. That's 14degC/W. We have 5W dissipation, so that's a temperature rise of 5 x 14 = 70C and an ambient temperature of 45C, so a max junction temperature of 115C.
115C still squeaks under 120C (but is quite comfortably under 150C).
If it was unacceptable, we'd have to consider reducing the dissipation (either lowering current or reducing the voltage drop across it) or finding other ways to improve the heatsink (forced air -- a fan), or limiting the maximum ambient temperature, or perhaps moving to an alternative circuit that dissipates less power (switchmode power supply), etc.
