I received hundreds of genuine Philips Luxeon SuperFlux LEDs for free from a nice guy on another website for helping him design a project.

The LM7809 has an output current of up to 1A if you cool it enough.
You will make strings of 3 LEDs in series and in series with a 100 ohm resistor (if all the LEDs are about 2.2V) which is a current of 24mA. The LM7809 can power up to 40 of these strings for a total of 120 LEDs.

I hope your cheap LEDs do not all fail at the same time.

I would never put cheap Chinese junk on my car, especially not lights.
I don't know how many LEDs you are using so I don't know how much current will be in the regulator. If it is half an Amp and the alternator is charging the battery at 14.4V then the regulator will be heating with (14.4V -9V) x 0.5A= 2.7W. A fairly large small heatsink should be used. Bigger than this little one:

Originally Posted by cantfindausername

So to reduce the heat build up in the regulator, could I use a 12v regulator?

My thinking here is to stop the LEDs being fried when its producing >12v, but will just allow the lights to dim a bit when producing <12v, i.e when the engine isn't running?

The LEDs will dim a lot. The 9V regulator still works when its input voltage drops to 11.1V.
An ordinary 12V regulator starts dropping its output voltage when its input drops to 14V.
A low-dropout 12V regulator still works when its input is 12.5V.
With a 12V regulator then 4 red LEDs can be connected in series, then the resistor value will need to be re-calculated.