As the new Nature Physics paper says, various explanations are possible:
First, the base of the drop is deformed by the presence of the ratchet below, which induces a modulation of its curvature and consequent Laplace pressure gradients4. Second, a wave propagates from the trailing edge to the leading edge of the drop, making the transport of matter possible in the direction of its motion. Third, a Leidenfrost drop is likely to oscillate spontaneously20; for each elementary rebound, part of the kinetic energy can be transferred from the vertical to the horizontal direction because of the slope of the teeth. Fourth, the Marangoni effect related to temperature differences might cause a displacement, as seen in Marangoni-levitating drops heated asymmetrically using a light source21. Fifth, as the drop loses material, this gas flow might provoke a motion provided it is made directional (or rectified) by the presence of the teeth.
The fifth explanation differs from the other four in that it doesn't rely on the droplet being fluid -- all the others depend on the deformability of the droplet. So the authors tested this by repeating the experiment with dry ice. Since dry ice sublimates, it too should levitate on a cushion of gas when dropped onto a "skillet" with a sufficient temperature gradient. But it isn't liquid, so it can't, e.g., "modulate its curvature."
In the event, a piece of dry ice propels itself exactly like a droplet of water; this establishes that gas flow is behind the self-propelling. How does this work?
As the gas moves towards the step, that is towards a sudden contraction in the fluid channel, the flow resistance is higher than in the reverse direction23. As a consequence, the vapour will mainly escape along the smallest slopes of the texture, which propels the Leidenfrost body in the direction shown in Figs 1 and 2 (jet thrust). This interpretation was confirmed by forcing contact between the hot ratchet and a disk of dry ice, thus printing the tooth pattern on the bottom of the disk, and observing a similar motion with this textured disk on a hot flat solid.
In other words most of the evaporated carbon dioxide moves up the gradual ramps, i.e., "with the grain" of the ratchet, so (by Newton's third law) the levitating solid is pushed in the opposite direction.
In addition to the appeal of all simple phenomena that could have been discovered centuries ago, this work is a neat example of the scientific method in action, and esp. of the value of clever controls. This is an aspect of good scientific practice that doesn't get the attention it deserves; the original Freakonomics book is actually the only piece of popular writing about anything where I've seen it covered in any detail.
 I don't know what the technical difference is between a droplet and a drop. No one ever seems to talk about drops of water in physics.