Clearance is the shortest distance through air between two conductive parts. Creepage is the shortest distance along the surface of the insulation between them. Clearance guards against the air breaking down; creepage guards against current tracking across a contaminated or damp surface.
Both depend on the working voltage, but creepage also depends on the pollution degree of the environment and on the insulating material, which is graded by its comparative tracking index (CTI). Clearance depends on the voltage, including any transient overvoltage, and on altitude, because thinner air breaks down more easily. The distances are set by safety standards such as the IEC 60664 series and by product standards built on it.
In practice, either one can be the limit. A small-pitch connector often runs out of creepage first, especially in dirty or humid conditions. The manufacturer's voltage rating assumes particular conditions, so check the pollution degree and altitude stated on the datasheet against your own, and never assume that a rating for one condition carries over to another.
