Shortly after finishing school, I came across this book - I don't remember what its called, but it showed me to model thermal values as circuit elements.

simulate this circuit – Schematic created using CircuitLab
Calculate what your total power dissipation from your regulator is and sub in that value for Pd.
Rjc is the junction to case thermal resistance. This is given in the datasheet.
Ta is the max ambient temperature the device may operate at.
Rsa is the surface to ambient thermal resistance. This is given in the datasheet as well, but this is the only parameter you can change. If the default values are not sufficient, you can add a heat sinks thermal resistance here.
The node labelled junction temperature, is maximum desired temperature. Basically what you are doing, is solving this circuit as you would if it was currents and voltages.
Voltages = temperature.
Currents = Power
With this, you can calculate what minimum heat sink you would need.
Edit
\$ \theta_{JA} \$ = thermal resistance from junction to air.
However \$ \theta_{JA} = \theta_{JC} + \theta_{CA} \$.
In the schematic above Rjc is is only from the junction to the case. Rsa is the from the case to the ambient.
In the datasheet, they have given you RJC and Rsa ( \$ \theta_{JA} \$ ) as well as they have given you \$ \theta_{JC} \$
Edit again
Let's work through some numbers.
Maximum junction temperature of your device is 150C. So lets derate and lets say 100C.
That is our desired junction temperature.
Your power dessipiation is 5W.
Rjc = 5W/C
Max ambient is 35C.
Solve for Rsa.
$$ Tj = R_{JC} * Pd + R_{sa}* Pd + Ta $$
$$ \frac{Tj - Ta}{Pd} - R_{JC} = R_{SA}$$
Substituting values in
$$ R_{SA} = 8W/C $$
Do we need a heat sink ?
The datasheet says that the \$ \theta_{JA} = 65\$ so that means that \$ \theta_{CA} = 60 \$.
The minimum value we need is 8W/C, so clearly we need a heatsink.
IF the calculated value of Rsa was 65 or more, then then no heat sink would be needed because the thermal resistance of the device itself would be sufficient enough to dissipate the heat.