Linear supplies can be about as efficient as switching supplies--an on rare occasions even more efficient--in cases where the input voltage will always be slightly above the required output voltage. Unfortunately, if the input voltage is only slightly above the required voltage, then a small dip in the input voltage will leave a supply unable to maintain the required output voltage, and a small increase in the input voltage will cause a huge relative increase in the amount of power a linear supply will have to dissipate.
The advantage of a switching power supply is that it will be able to offer good performance over a wide range of input voltages. Even though, as darudude notes, many supplies have a somewhat narrow range of conditions under which they will achieve optimal efficiency, in most cases such limits stem from the fact that many supplies have a certain minimum amount of power that they will draw whether or not the load requires it, as well as a certain amount of power that they will consume beyond what the load takes.
If a 12V to 5V converter is 90% efficient when supplying one amp, but draws a minimum of 1uA from the source, then it efficiency when driving a 10nA load would be pretty pathetic (less than 1%) but the amount of power it would waste in that situation would be only 12uW--far less than the losses when supplying a full amps (where it would waste about 0.56W). If a battery-powered device will need to supply a load that consumes a full amp for one 1 seconds each week and otherwise draws 10nA, the average current draw would be about 1.7uA, of which 1.0uA would be a result of the baseline current draw, making the overall efficiency about 40%. If, however, the load consumed a full amp for ten seconds each week, the average current draw would be about 8uA and efficiency would improve to be about 80%. With the one second-per-week load, reducing the current drawn during the idle times might potentially double battery life. With the ten-second-per-week load, however, battery life would be limited by the need to supply real current to the load even if the idle power consumption could be reduced to nothing.