I can't claim to be an expert, but as I understand it, air gauges are used not just for barrels, but for gauging all sorts of holes. Basically, a air gauge acts like a piston in an automobile engine. One end of the barrel is pressurized and a precision plug passed through it. The amount of air escaping around the plug is measured. The instrument is calibrated for the desired tolerances (range of air flow) and if the amount is too great or too small, the part being inspected fails, being out of spec. Any parts of the barrel larger than others are easily detected as the air flow increases at that point.
Here is a pretty good discussion, not quite detailed enough in that area, but interesting.
http://www.riflebarrels.com/articles/barrel_making/details_of_accuracy.htm
Of course just using an air gauge doesn't prove anything. It is like saying something is "inspected" without saying what the inspection found. A maker can say his product has been "air gauged", meaning only that the test was run, not that the results were correct or even if they were that the product will meet the customer's expectations.
The problem is that, as the article says, gauging a barrel is just one of the components of getting accuracy. In the old days, when the Army sold M1903 match rifles with star gauged barrels (a star gauge was an early type of mechanical barrel gauge), they were considered the holy grail. Match shooters would stop just short of bloody murder to get their hands on one of those precious star gauged rifles. (Today they are collectors items and there are many fakes, some dating to the aforementioned desire.)
Anyway, the problem was that some of those rifles with the precision barrels had a problem - they wouldn't shoot worth a darn.
Jim