Heavenium violates the Second Law of Thermodynamics. You don't need fuel.
What?
The second law of thermodynamics states that the total entropy of an isolated system can never decrease over time, and is constant if and only if all processes are reversible. Isolated systems spontaneously evolve towards thermodynamic equilibrium, the state with maximum entropy.
[…] In all processes that occur, including spontaneous processes, the total entropy of the system and its surroundings increases and the process is irreversible in the thermodynamic sense. The increase in entropy accounts for the irreversibility of natural processes, and the asymmetry between future and past. […]
[…] Its first formulation is credited to the French scientist Sadi Carnot, who in 1824 showed that there is an upper limit to the efficiency of conversion of heat to work in a heat engine. This aspect of the second law is often named after Carnot. — Wikipedia, used under CC BY-SA 3.0
Why?
All processes that require heat are either entropic in nature (e.g. cooking), or actually require a temperature difference (e.g. Sterling engines, solar panels). All natural processes that extract useful energy (aka do work) from a temperature difference also reduce that temperature difference. In short: without access to sunlight and the vacuum of space, you'll run out of usable energy sooner or later.
Heavenium, however, works on absolute temperature, like entropic processes, but provides useful work, which you can normally only get from a temperature gradient. It's a negentropy source. This stuff's worth more than the Sun.
How?
There are countless ways of making use of this, but I'll start with the simplest to explain.
Heat pump in a box
Make a pulley. One end of the pulley should be a box containing some fancy technology and some Heavenium (I'll get to that in a sec); the other should be weighted so that it goes up when the Heavenium is “off” and down when the Heavenium is “on”. Attach the pulley to a really tall tower.
In the box, wind up some clockwork, and attach it to a heat pump. Set the heat pump so that it'll warm up a compartment containing Heavenium and cool down a compartment containing hot water, then start it going and shut the box. The Heavenium box will go up. Use some of this energy to do work (e.g. winding up some more clockwork). Eventually your clockwork will run out, or your heat pump won't be powerful enough to heat the Heavenium to the critical threshold any more, and the Heavenium will run out of magical lifting ability; you know when this will happen in advance, thanks to your calculations, so you can switch to generating energy from the pulley going the other way.
If you use a Sterling engine to recover the energy from the temperature gradient the heat pump made, you will have:
- Cold water, and a cold box in general; and
- More energy stored in clockwork / used to do useful work than you started with.
With a sufficiently-powerful heat pump, you could start with regular old ambient-temperature water, cool it down, and generate energy for useful work. Of course, eventually, this energy would run out; friction and other losses would see it slowly lost to heat. But you can extract work from heat.
Your airship does not need fuel.
Heavenium engine
Okay, so maybe building a massive tower in the middle of your airship isn't actually all that practical. You need something more engine-like. Take a heavy flywheel, and put it vertically over a well-insulated Heavenium-containing oven (so that the rising side is lighter); insulation reduces the maximum power your heat pump system needs to have to get the Heavenium hot enough. (Frictional losses aren't all that important because a Heavenium engine uses heat as fuel – I still can't get over how overpowered this is!) Fuel this oven with a powerful heat pump (or chain of heat pumps) powered by the Heavenium engine. The energy will eventually get back to the heat pump no matter what you do, but you can speed it along by sticking the “cool” end(s) of the heat pump on whatever's generating most of the frictional losses.
Now simply heat up the oven to the critical temperature, spin the engine a bit to get it started, stick a fan on the end and you're away!
When?
Heat engines have been known since antiquity. The first refrigerator (requiring pretty good heat pumps) predates the industrial revolution by over 75 years. While this technology might not be immediately apparent, since the Second Law of Thermodynamics hadn't been invented yet, anyone who understood fridges and had heard of Heavenium would probably be able to figure it out, and it wouldn't take much longer to develop heat pumps good enough that this would be viable.
Unless, of course, you need to get the Heavenium really hot. Then this is right out.