I'll be honest, I've mostly forgotten the reason.
I shall try to vaguely reconstruct it here - and I may be wrong.
As far as I know, a wing (or an entire plane) is designed towards achieving certain performance. That is measured in coefficients: Lift and drag coefficients (and the fraction between those, too).
For a wing of chord length 1 unit, these coefficients are essentially the force (lift or drag) divided by 1/2 times the air density times the velocity squared.
At high altitude, the density is lower.
This means two things:
1) in order to produce the same lift (or drag) at the same angle of attack, you have to fly faster. (the denominator of the eguation has to stay identical, so if density goes down, velocity squared has to go up to compensate)
2) if thrust = drag (steady flight), you get more speed out of the same amount of thrust, at higher altitudes.
Now the problem is: I've forgotten all of my propulsion knowledge. I believe that jet engines were the ones that produce the same thrust force, no matter which speed they're flying at (until they reach speeds close to Mach 1), and that turboprops are the ones that produce thrust that varies with airspeed. Now I suspect there's a further complication: probably the fuel consumption of an engine is not independent of air density and altitude (i.e. it may be higher or lower at cruise altitude, but I forgot which it is).
However, for the sake of an oversimplified (and therefore probably inaccurate) example:
Imagine you have an engine that produces a certain amount of force X, regardless of the airspeed. That means, your airplane can accelerate until it reaches a speed where its drag equals X. At high altitude, that speed is much higher than on the ground. So if the only factor determining fuel consumption is the output thrust force, then you are effectively using less fuel per distance flown if you fly higher. You get to travel further on the same gallon of fuel.
Now can someone clear up what the relation between fuel consumption, thrust force, and altitude is for jet engines? Because that's the bit where I'm most likely to have gone wrong in my assumptions, I think.
Sorry if I made any mistakes, or anything was not clear.