I've always thought that it was because the frictional force on the tire was increased due to the bulging of the tires increasing the surface area in contact with the road. However, a colleague of mine reminded me that frictional force is independent of surface area. Why then is fuel economy decreased when tire pressure is low?
Lower pressure increases surface contact and increases static friction, and static friction does not involve heat loss, so that is good. But rolling friction is not good and does involve heat loss.
Rolling friction heating is due to the inelastic deformation the rubber of the tire experiences when it is in contact with the road. See this article on rolling resistance from Wikipedia: https://en.wikipedia.org/wiki/Rolling_resistance
When the rubber is in contact with the road for each revolution, it is compressed, it then expands when it leaves the surface. The compression and expansion is not perfectly elastic, thus there is heat loss in the form of friction. The lower the tire pressure, the more rubber that is in contact with the road for each revolution, and the greater the friction heat loss. These increased heat losses add up to lower fuel economy.
Hope this helps.
Static friction does not actually reduce your fuel economy. Without it, your wheels would slip, so it is a good thing.
What causes the loss of fuel economy is rolling resistance. This is due to hysteresis; energy lost due to the cyclic deformation of the tyre as it rolls.
It's not a great analogy but imagine the partially inflated tire as a disc with the axel off centre. When rolled the axel will oscillate up and down - i.e. some energy is lost from being able to contribute to the forward motion.
In your case the axel doesn't bob up and down but energy is lost to reshaping the tite from bulging on one side to bulging on the other with each half revolution.
When using pneumatic tires, the "rolling friction" represents the effort required to continuously reshape the tire. The lower the pressure in the tire, the greater the amount of deformation as it rolls, and thus the more work will be required to achieve such deformation. If one were to inflate tires sufficiently that they would barely deform as they rolled, this friction would be greatly reduced (thus improving fuel economy) but the performance and handling advantages of pneumatic tires would be sacrificed.
If one were driving a car with absolutely rigid wheels, then every little bump in the road surface would cause the force between the wheel and the ground to be increase as the car hits the bump, and then decrease as soon as the wheel is over. Because stopping force is limited by the breaks as well as traction, momentary increases in traction won't improve it, but momentary decreases in traction will reduce it. Pneumatic tires minimize this problem because the contact area can be continuously reshaped to minimize the increase in force when hitting a bump, and thus the inevitable reduction in force afterward.
The reason that tire pressures are stated on vehicles rather than tires is that the amount of pressure needed to limit deformation to the optimal level will vary depending upon a vehicle's weight. Ideally, tires would supply a table of recommended inflation pressures based upon vehicle weight, but most vehicles are intended for use with a relatively narrow range of tire sizes, and tires of a given size will tend to have similar inflation recommendations. The exact optimal pressure for different manufacturers' tires won't be identical, but most tires will perform reasonably well over a sufficiently large range of pressures that a pressure chosen for a typical tire will usually work reasonably well--even if not quite optimally--for others tire of similar size.
I have a slightly different intuition on this point than the other answers, which may help.
Imagine you are riding a skateboard or roller skates (with very hard wheels) across a soft rubber surface. In this case, it is not the wheel that deforms, but the surface:
The wheel/surface interface deforms by exactly the right amount to where the load on the wheel is balanced by the upward force of the surface.
Now, for your wheel to advance by the next increment, it has to go "uphill" to get out of the dent that it has caused itself in the surface. You can think of the wheel's progress as being a series of "climbs" out of the dip, followed by the surface collapsing vertically again under the weight. Of course in reality, your progress will not take place in this manner, you will be pushing a zone of compressed rubber in front of the wheel, but the result is the same. If you have ever tried to ride a skateboard over grass or push a pushchair on a beach, you will have experienced this problem.
For a car (and most other wheel/surface interfaces) the wheel is softer than the surface, so the wheel deforms, not the surface:
This is why it is so much more efficient for bicycles to have larger diameter wheels; the flat-spot on the bottom of the wheel can be as big as necessary, but the angle between the flat-spot and the next millimetre of tyre will be correspondingly smaller, the bigger the wheel:
Also, the "hill" that the smaller wheel has climb is far steeper than the larger wheel, as shown by the angles A and B.
Finally, I think it's a bit abstract to think about fuel-consumption. You should just imagine how much harder it would be to 1) Ride a bicycle with flat tyres, 2) Push a car with flat tyres. It would take more energy. In your car, the energy comes from your petrol-tank, hence, you get a lower mpg figure when your tyres are under-inflated.
Friction being independent of surface area only applies to smooth surfaces. Roads are rough: the tire is constantly being deformed by irregularities in the road. You can see this in real time if your car has a fairly sensitive fuel economy meter: all else being equal, the rougher the road, the worse the fuel economy.
For a practical demonstration, consider two extremes: the high rolling resistance of wide, low pressure tires used by off-road vehicles (and wannabees), and the very low rolling resistance of the inflexible steel wheel on steel rail of trains.
The street moves with constant linear speed under the tire, but the outside of the tire moves with constant angular speed. The more tire has contact with the road at one point of time, the more discrepancy between moving parts of the tire and the moving road occurs. This discrepancy is to some degree resolved by ruboff. It causes loss of energy and material.