What you need is the thermal resistance. You've done the hard part and found a decent data sheet, so you know this is 19 deg C per Watt. That means for every Watt of heat generated by the device, it's temperature will rise by 19 deg C above the surrounding air when mounted on this heatsink.
Also there is a thermal resistance associated with the device itself, which is 2 deg C per Watt. So it will actually be 21 deg C hotter than the surroundings for each Watt of power it dissipates.
How many Watts does it dissipate? Well, if the input is 6V and the output is 5V, then there is 1V drop across the device. When it is delivering it's maximum load of 1 Amp, it looks like a resistor with 1Volt across it and 1 Amp passing through it, so it dissipates 1 Watt.
When the air is 25 deg C, it will run up to 21 deg C warmer, ie. 46 deg C, which is well below the safe operating temperature of 125 deg C (again from your datasheet.)
Now you may want to be careful and say, what if the output is accidentally shorted? Then the current could rise to as much as 3.5 A. (maximum self limiting current of 29150) Then the dissipation would be,
6V (input - short output) x 3.5A = 21 W
Then the temperature rise could reach 21 x 21 = 440 deg C so the chip could fry.
That's a worst case value, but even the typical short cct current is 2.1 A, which gives 264 deg C.
This sounds bad news, but thermal inertia (not on the datasheet I think) is on your side. It takes a finite time for this temperature rise to occur. If you put a device with a smaller thermal inertia into the circuit, its temperature will rise faster. This is a fuse and with a bit of luck this will blow before the chip gets hot enough to become a fuse itself!
The alternative to a fuse would be a heatsink which would limit the temperature to 125 deg C. So if the air is about 25 deg, we have 100 deg to play with. Taking the max dissipation of 21 W, we can afford a thermal resistance of 100 / 21 = 4.8 deg per Watt. Now the chip is already 2 deg / W so the heatsink must be no more than 2.8 deg/W. The CPC selector allows you to search for this, though the larger heatsinks I found were not intended (but might well work) for TO220.
But a fuse is the way to go! I just mentioned this to show the calculation.
So thermal resistances, max operating temperature and max dissipation are the key factors. The calculations are just like electrical resistance calculations.
PS. Í just looked back at the datasheet to see if there was any data at all about thermal inertia, and noticed that P.19 actually explains thermal design. (I haven't checked to see if they agree with me!)