How is clearance affected by altitude (air pressure)?

Well, to start with, "creepage" has nothing to do with the air at all — it relates to currents flowing in surface contaminants.

"Clearance" has nothing to do with the conductivity of air, but rather its ability to prevent an arc from occurring. Paschen's Law provides some insight into this issue. I got there by searching "air arc voltage vs pressure" — there are other useful resources there, too.

Clearance has less to do with the working voltage of the circuit, and more to do with the level of expected transients. Yes, a circuit with a given clearance will break down more readily at high altitude for a given level of transient, but this is rarely an issue that requires a design change.

It would change the length of the clearance, so if the electrical design is in a rocket or a high altitude balloon (or airplane), then it's something to take into consideration. Here is a description of what happens with arcing with respect to altitude.

The answer is both, the arc gap decreases from sea level to ~45 km and then increases after 45 km. However, most of us only care about 0 to 3000 m (or 3 km).

The curve on the chart above tells the story. At sea level, about 30,000 VDC is required to initiate an arc across the electrode gap. At 47,000 ft. the arc level drops to about 1200 VDC. Accordingly, the worst altitude is 150,000 ft., where only about 300 VDC will arc across the electrodes. Electronic Countermeasure Systems (ECM) and other radar and electronic systems aboard aircraft require high voltage connectors and cable assemblies to function at altitudes up to 70,000 ft. with 1,500 to 40,000 volts applied. Missile-borne ECM systems raise the requirement to 150,000 ft..

Source: Teledyne: Paschen’s results

Creepage and clearance simply define a minimum safe distance that conductors can be placed apart on the PCB to prevent arcing. This takes into consideration elevation (up to 3000 m or 10 kft), since IPC standards are for consumer products which are generally not used above 3000 m, the standards are only calculated for that range. What's also interesting is China does have a different standard (GB 4943.1-2011) that has creepage and clearance to 5000 m (because they have higher elevations).

I haven't checked, but I'd imagine that the pollution degree would have the greatest effect on creepage and clearance distances and then air arcing would come next. Dirty and humid surfaces are much more conductive than air. I'd imagine aerospace (airplanes) requirements are different, but I am not familiar with them (only space where there is no air). If you're designing a product, then follow the IPC standards, and if you're designing a high-altitude circuit for a balloon, then add a sufficient margin.

The chart to the left is adapted from columns B1, B2, B4 of IPC 2221B Table 6-1. It lists recommended minimum spacing between internal and external conductors as a function of peak working voltage level for intended use at altitude below 3050 meter (10.007 feet). The official IPC table also provides the numbers for external conductors at elevations >3050 m as well as requirements for assemblies, which I omitted here

Source: PCB clearance