12V -> 5V 1A using L7805CV
The data sheets indicate .33uF on the input, and .1uF on the output. Ceramic caps are probably what you want there. Total cost of both on Digikey is around $.60 in singles. If you expect any current surges on the output, you could add a tantalum or electrolytic to the output to handle them.

The caps are a trivial issue compared to the heat sink. For a linear regulator, current in is current out. Input power is 14V * 1A, or 14W. Output power is 5V * 1A, or 5W. The remaining 9W is heat, and 9W in a package that small is a lot of heat. Data sheet says the maximum junction temperature the device can handle is 150C. The data sheet lists the junction-to-ambient thermal resistance is 50C/W. Dump 9W into that and your junction will go 450C above ambient. Far, far above its maximum limit. The semiconductor junction in the device will melt, probably within seconds.

You need a heat sink to reduce the thermal resistance between the junction and the ambient air. Maximum safe thermal resistance between the junction and ambient is (150-40)C/9W = ~12 degrees per watt. Junction-to-case thermal resistance is listed as 5C/W. Case-to-sink thermal resistance for a TO-220 package (not listed in this data sheet) is commonly somewhere around .5C/W. That means your sink-to-ambient thermal resistance can't be higher than 6.5C/W. Looking on Digikey, their cheapest common sink for a TO-220 that gives you any overhead at all is the 7023B which costs $1.39, twice the cost of your regulator! And now your footprint is larger because of the heat sink.

You can make the entire system much smaller and more efficient by using a switching regulator, and eliminating the need for a heat sink. I recommend the 78SR-5/1.5, available at Mouser for under $4 in singles. It costs a couple dollars more than the regulator and heatsink combination, but it greatly reduces the footprint of your circuit, and it's more energy-efficient. You don't have any appreciable heat to worry about, and the current out of your battery is now cut in half. They recommend larger capacitors, ~10uF on both input and output.

I've used these parts in production electronics and had no problems. They're much cheaper than the competing V78xx line of switching regulators, and the footprint is smaller, allowing them to drop into an existing circuit where a 78xx linear would go.

So for an extra $2 or so, you've made the package smaller, and made your battery last over twice as long. Unless you're building a million of these things, that $2 is going to break you, or you don't care at all about battery life, I'd suggest this is the way to go.