I'm building a project that needs both 5V and 12V rails which will draw about 1A on the 12V and 0.5A on the 5V. I was thinking of using a 7805 to produce the required 5V but this could generate some significant heat. I am not so much asking if it is acceptable to use a 7805 (I just need a mini heatsink), but rather: are there any ways of doing it cooler? Any tips would be great.
Instead of using a linear regulator, which has relatively low efficiency (~50%), use a switching DC-DC converter (efficiency around 80-90%). A decent one to start with is National's "simple switcher." It looks like the LMZ12001 would do the job-- up to 1 A at 5 V, and it accepts input voltages from 0.8-20 V.
One of the main issues with regulators like the LM7805 (and linear regulators in general) when you step down from large voltages is that a lot of the energy is dissipated as heat. If you are limited to passive cooling only and you have some significant power draw from your load, you might risk thermal overload. Fear not, because if you are willing to put up with a bit more complexity and cost there is another option: Switching regulators, specifically in this case buck converters, which work off of a completely different principle. Depending on what your other requirements are, like noise, stability, EMI considerations, you might look into some of the highly integrated switching regulator modules offered by TI, like the PTN78000W family. That part in particular is nice because of the adjustable output, so you can produce a variety of supply rails off of one part.
Switching regulators (aka DC/DC converters) can step down 12V to 5V step without generating too much heat. Since you only need 2.5W on your 5V, don't think you need a heatsink too.
Lineage has some good DC/DC regulators: http://www.lineagepower.com/category.aspx?NID=5e1812f4-fb02-49f4-ba31-6e312010f40d
I'm assuming here that you need a non-isolated converter ie. your 5V does not need be electrically isolated with a transformer from the 12V. Non-isolated dc/dc are cheaper and smaller.