What is the coldest substance?

Liquid air. It is the coldest substance known. It takes an intense cold to produce it, and it has to remain cold much as ice is cold, only very much more so, as long as it is liquid air.

birdnature.com/jan1900/air.html no longer exists

Liquid hydrogen is the coldest substance known to man, minus 400 degrees.

http://transcripts.cnn.com/TRANSCRIPTS/0607/03/ltm.08.html

ALSO: A Bose–Einstein condensate (BEC) is a state of matter of bosons confined in an external potential and cooled to temperatures very near to absolute zero (0 K, ?273.15 °C, or ?459 °F ). Under such supercooled conditions, a large fraction of the atoms collapse into the lowest quantum state of the external potential, at which point quantum effects become apparent on a macroscopic scale.

https://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_condensate

Hydrogen liquifies at −252.87°C (−423.17 °F for non-scientific places...) However, the Boomerang Nebula is recorded at −272.15 °C and that's even colder than the universal background radiation. http://apod.nasa.gov/apod/ap071228.html for a nice filter coloured pic.
In theory, any substance can be cooled to near absolute zero if you try hard enough. Also, absolute zero can't be reached, but they seem to have got down to 700 billionths of a degree kelvin (the nebula I referred to is at 1°K). Thus, there is no single substance that is the coldest. The record holder is whatever they worked on at the time. Hydrogen just happens to have one of the lowest temperatures at which a transition occurs (i.e. gas to liquid). Most other things are solid by then, but that doesn't stop them being capable of temperature reduction. https://en.wikipedia.org/wiki/Absolute_zero
Don't be fooled by negative temperatures. Absolute zero is 0°K, and that is regarded as the end of the line. (That's why it's 0 degrees K. The other scales zero at much higher temperatures. Think of it like bank accounts - F and C are current accounts where you can have an overdraft. K is a savings account where you cannot go below a zero balance.) There are so-called negative temperatures involving K. This is a scientific trick of the trade (like the square root of -1 in maths) and doesn't mean below absolute zero. https://en.wikipedia.org/wiki/Negative_temperature for what it does mean.

The coldest substance on earth seems to be liquid or solid helium--they have trouble telling them apart, apparently.

"Unlike any other element, helium will remain liquid down to absolute zero at normal pressures. This is a direct effect of quantum mechanics: specifically, the zero point energy of the system is too high to allow freezing. Solid helium requires a temperature of 1–1.5 K (about −272 °C or −457 °F) and about 25 bar (2.5 MPa) of pressure. It is often hard to distinguish solid from liquid helium since the refractive index of the two phases are nearly the same."
https://en.wikipedia.org/wiki/Helium#Solid_and_liquid_phases

Can't say I understand much of that; I'm just looking at the numbers. And, yes, I noticed Storky's not limiting it to Earth, but he is limiting it to a [single] substance.