Why do jet engines get better fuel efficiency at high altitudes?
For a quick explanation, you need to know that


Thrust is the difference between the entry impulse of the air entering the engine and the exit impulse of the heated fuel-air mixture leaving the engine. Impulse is mass times velocity, and expressed with a mass flow $\dot m$, thrust T is $$T = \dot m \cdot (v_{exit} - v_{entry})$$
The exit impulse is increased by accelerating the airflow through the engine, and the acceleration is achieved by heating the air.
Each gram of fuel heats up a given mass of air by a certain number of centigrades. The definition of the energy content of fuels is given as the capacity to heat one pound of water by one degree Fahrenheit. The definition of one Calorie is similar but in metric units. Since the heat capacity of both water and air are almost constant at moderate temperatures, the starting temperature makes little difference to the absolute temperature increase when a given amount of energy is added.


Thermal efficiency

Thermal efficiency is the ratio between the mechanical work extracted as thrust and the heat energy spent on heating the air, and it is affected indirectly by the flight altitude. Please see the Wikipedia article on the Carnot cycle. This and similar cycles describe the workings of all combustion engines in thermodynamic terms. Basically, it says that the efficiency of a combustion engine cannot be greater than the temperature ratio between the temperature increase from ambient ($t_{amb}$) to the maximum temperature $t_{max}$ of the process, divided by the maximum temperature. All temperatures must be expressed as total temperatures, where 0° means 0&nbsp;K or -273.15°C. Operating in colder air makes the ratio bigger and improves efficiency.
$$\eta_t = \frac{t_{max} - t_{amb}}{t_{max}} $$

If $t_{amb}$ is 290&nbsp;K (16.85°C or 62°F) and the fuel heats up the air to 1400&nbsp;K (2060°F), the thermal efficiency according to the formula above is 79.3%.

At cruise altitude $t_{amb}$ is only 220&nbsp;K (-53.15°C or -63.7°F), and the same fuel flow relative to air flow will lift the maximum temperature only to 1320&nbsp;K (in reality even less; for more precise reasoning see below). Now the thermal efficiency is 83.33%! If the maximum temperature is maintained, both thrust and thermal efficiency will go up; the latter to 84.3%.

In reality, the total efficiency will be lower because we have not included propulsive efficiency, friction effects or power offtake by bleed air, pumps and generators. Propulsive efficiency describes how well the acceleration of air is performed.

Heating the fuel-air mixture

Burning a fuel-air mixture will add thermal energy to it, about 43&nbsp;MJ for every kilogram of kerosene (if we assume complete combustion). The isobaric heat capacity or specific heat of air (close enough, the mixture has very little fuel but lots of air in it) is 29&nbsp;J per mol and per K, so those 43&nbsp;MJ will heat 1000&nbsp;mol of air by 1483&nbsp;K. The heat capacity changes slightly with humidity and temperature, but little enough that we can consider it constant for this purpose. If the air starts at 220&nbsp;K, precompression in the intake will heat it to approx. 232&nbsp;K, further compression in the engine will heat it up to approx. 600&nbsp;K if we assume a compression ratio of 25, and this is the temperature at the entry of the combustion chamber.

Those 1000&nbsp;mol of air weigh about 29&nbsp;kg, and adding a full kilo of fuel and burning the mixture will heat it to 2083&nbsp;K. If you want more details about the parameters in a typical jet engine, please see the diagram in this answer. Since the mixture picks up speed as it burns, the fuel mass is also heated and combustion is never complete, the maximum temperature given here will not be reached in reality.

If we start on the ground with an air temperature of 290&nbsp;K, the temperature in the intake would drop slightly because we will not be flying fast enough for any precompression to happen in the intake. Now the compressor will heat the air to 730&nbsp;K, and again adding and burning that kilo of kerosene will heat 1000&nbsp;mol of air to 2213&nbsp;K. Ideally.

In reality, the engine control will see that the limit temperatures are not exceeded, but here we can play with the numbers as we like. The exact values will certainly be slightly different (more frictional heating in the compressor, heat loss to the outside, slight drift in specific heat with temperature), but the gist of the explanation is correct.

Explanation in layman's terms

Burning the fuel-air mixture heats it and makes the gas expand. This happens at nearly constant pressure and in a restricted volume, so the only way to make room for this expansion is for the gas to flow faster. Nearly constant pressure means that the density of the gas must decrease. The density ratio between the heated and the unburnt gas is proportional to its temperature ratio, measured in absolute temperature.

However, the amount of fuel burnt determines the absolute temperature increase, the difference in degrees between the burnt gas inside the combustion chamber and the unburnt gas at the intake. For a given amount of fuel, the temperature ratio which can be achieved with an absolute temperature increase becomes smaller the higher the temperature of the unburnt gas is. Thus, efficiency decreases with a higher temperature of the intake air.