Why is the energy density of gasoline so high? We sometimes play a game in my family whereby we trace the energy for a device back to it's source:


*

*The Xbox got power from the wall.

*The wall got power from the local transformer.

*The transformer got power from the coal plant via the power lines.

*The coal plant got power from the turbines.
...etc.


On and on until we've reached the core of the sun in dinosaur times. But my son stumped me the other day...what it is it in particular about petroleum (and gasoline) that makes it so high in energy density?
Secondarily, I presume that gasoline has other qualities that make it a good fuel, e.g., not exploding spontaneously without significant energy. What are these other qualities? 
Finally, if energy input were not an economic consideration, and we only cared about energy density and the other Goldilocks factors, is there a better fuel? Or is gasoline not only the best actual fuel, but the best theoretical fuel?
 A: I will add an interesting flavor of physics to spice up Martin's excellent chemistry answer and which is in line with your original reasoning on how to trace energy content.
When chemical reactions take place and bonds form, break, and reshape, the atom nuclei don't change in any way. What happens is that the electrons jump between atoms or groups of atoms and change orbits. The different orbits are bound by different energies and you can start with a configuration of atoms and electrons and end up with another configuration but the total energy stays the same. This is really all there is to it, and thinking about that will give you a lot of intuition in particular with "energetic" chemistry.
The "trick" with using molecules to store energy is that, like you wrote yourself, apart from the energy density, sometimes you want to control the movement of the electrons in a very tight way and sometimes you just want as much kinetic (heat) energy quickly.
For example in the biological mitochondria, the electrons of the molecular by-products of glucose metabolism are delicately bounced around until they end up orbiting CO2 molecules, with their initial potential energy being deposited as high-energy bonds on ATP molecules (used in the body as energy storage) and as little energy as possible lost as kinetic energy (heat). This process is actually called an electron transport chain and is quite complicated and, should you look at the actual proteins and molecules involved, surprisingly mechanical in some ways :)
On the other hand, if you burn glucose in a fire, you also end up with exactly the same CO2 end product, but the electrons' paths there are chaotic and create a lot of kinetic energy (heat) and no ATP or other useful intermediary. This would be quite useless in a human body, but good for creating engines that depend on heat (or the resulting expansion of gas volume).
Regardless of the form of electron transport in the above examples (or if you insert gasoline in a similar reasoning chain), the fascinating fact is that the actual energy chain starts with electrons in "high" orbits around some atomic nuclei due to photons from the sun for example, and can be traced to end up at a "tighter" orbit around some carbon and oxygen atoms a billion years later! 
Caveat: obviously electrons don't carry individual names, they are quantum mechanically identical and are exchanged and transported as such. The "orbits" are not classical satellite orbits around nuclei either. But the basic principle is still sound.
A: Gasoline is just a reasonably liquid hydrocarbon which is easy to evaporate on demand. That's what makes it useful. It's energy density is no more than any other hydrocarbon.
ADDITION: The linear alkanes all have about the same energy density per carbon atom, because the middle bonds are all identical, with the exception of methane, ethane, propane, butane where the edges are a significant fraction of the molecule. Pentane is barely liquid-- the inter-molecular Van-Der-Waals forces which keep the liquid together scale linearly in the length. The 6-7-8 carbon alkanes are good liquids that are not too explosive, but evaporable enough to use in an internal combustion engine with cheap misting injectors.  Past 9 carbons, you get a liquid that is too stable and is increasingly viscous, and at around 18 carbons you get a solid. You can find the information here: http://en.wikipedia.org/wiki/Higher_alkanes
A: Bonds - lots of bonds
Chemical reactions take in energy to break bonds and give off energy when they make bonds.
Big organic molecules like those in petrol have lots of weak carbon-carbon and carbon-hydrogen bonds which don't take a lot of energy to break.
But when it burns the combustion products make lots of very strong Carbon-Oxygen and Hydrogen-Oxygen bonds in CO2 and Water, these bonds give out a lot of energy when they form.
This is also explains why petrol/gasoline (and Diesel, Methane etc) with both Carbon and Hydrogen have higher energy densities than coal, which is pure Carbon. The extra H-O bonds formed by making the water releases a lot of energy.
edit: to answer your second question. Gasoline (or better still diesel) is widely available, cheap to extract and process, easy to transport, relatively safe and non-toxic to handle and the energy can be easily extracted with high efficiency(diesel engines can extract >50% of the theoretical chemical energy). And you can even manufacture it from sunlight!
