They work by laser ablation. Basically, the laser is bright enough and focused enough that anything that absorbs the light strongly will get heated to a plasma.
A CO2 laser can put out ~1000 watts of power in the infrared (10 µm) that can be focused to a strip or spot smaller than a millimeter. A material that absorbs at that wavelength will be heated very quickly. At lower powers you can use this for laser engraving. But for rust removal you can dump enough heat into the rust to heat it to a plasma.
Now, why doesn't the laser continue to burn away the iron underneath the rust? Because metals reflect light very well, especially in the infrared. I found this plot showing how at 10 µm even iron makes a very good mirror. So once the rust burns off, the laser reflects off the iron rather than heating it up