Efficient low power regulation? i.e. 9 -> 5 Volts

Linear regulators like the 7805 are inefficient, and more so when the input voltage is higher. It works as a variable resistor, which varies its value to keep the output voltage constant, here 5V. That means that the current consumed by your 5V circuit also flows through this variable resistor. If your circuit dissipates 1A then the power dissipation in the 7805 will be

\$ P = \Delta V \cdot I = (9V - 5V) \cdot 1A = 4W \$

4W in a single component is rather much, the 5W in your circuit will probably be distributed over several components. It means that the 7805 will need a heatsink, and that's most often a bad sign: too much power dissipation. This will be worse with higher input voltages, and the efficiency of the regulation can be calculated as

\$ \eta = \dfrac{P_{OUT}}{P_{IN}} = \dfrac{V_{OUT} \cdot I_{OUT}}{V_{IN} \cdot I_{IN}} = \dfrac{V_{OUT}}{V_{IN}}\$

since \$I_{OUT} = I_{IN}\$.
So in this case \$\eta = \dfrac{5V}{9V} = 0.56 \$ or 56%. With higher input voltages this efficiency will even get worse.

The solution is a switching regulator, or switcher for short. There are different types of switcher depending on the \$V_{IN}/V_{OUT}\$ ratio. If \$V_{OUT}\$ is less than \$V_{IN}\$ you use a buck converter.
While even an ideal linear regulator has a low efficiency, an ideal switcher has a 100% efficiency, and actual efficiency can be predicted by the properties of used components. For instance there's a voltage drop over the diode, and resistance of the coil. A well designed switcher may have an efficiency as high as 95%, like for the given 5V/9V ratio. Different voltage ratios may result in somewhat lower efficiencies. Anyway, 95% efficient means that the power dissipated in the regulator is

\$ P_{SWITCHER} = \left(\dfrac{1}{\eta} - 1\right) \cdot P_{OUT} = \left(\dfrac{1}{0.95} - 1\right) \cdot 5W = 0.26W \$

which is low enough not to need a heatsink. As a matter of fact the switching regulator itself may be in a SOT23 package, with the other components, like coil and diode SMDs as well.

The most efficient way would be to use a Buck Converter which is a type of Switching Regulator.

This type of regulator is far more efficient than a linear regulator, as it converts the power rather than intentionally dissipating the extra as heat.

Wasted power in your example if your circuit is drawing 100mA would be roughly:
(9V-5V) * 0.1A = 0.4W
Wasted power at 1A it would be around (9V-5V) * 1A = 4W.
This will be only about 55% efficient compared to maybe 80-95% efficiency for a switching regulator.

Here is an example part picked at random.
Some more examples here (select different check boxes to refine the search - I just selected 5V output)