Ambient air is approximately 78% nitrogen, a bit less than 21% oxygen, and a bit less than 1% argon; this doesn't leave much room, hence the term "trace gases" for everything else.
The literature indicates that 93% nitrogen yields measurable results. Air is approximately 78% nitrogen, leaving 22% of gases we don't want in the tire. Standard atmospheric pressure is approximately 14.7 psi. Pressurizing an "empty" tire to 75 psi with industrial grade nitrogen (99.5% minimum, but typically higher) reduces the non-nitrogen component to a bit over 4%, leaving 96% nitrogen. Dumping this and repeating the process reduces the non-nitrogen component to roughly 1%. Purging once should be sufficient: twice probably gets us to the best we can hope for, as subsequent purging only reduces smaller and smaller fractions.
The nitrogen machines in tire shops are concentrators, separating nitrogen from ambient air. They don't pull a vacuum in the tire, but rather fill to a set pressure with nitrogen from the concentrator. That's why the technician checks the concentration in the tire after the set pressure is attained. They typically only fill the tire to the working psi, reducing pressure and refilling (similar to the process above) only if the concentration is less than 93%. They will tell you that 93% is all you need, which is technically correct, but I think that they avoid fully purging to extend the service life of the concentrator columns. (Seems a bit cheap to me...)
By the way: The guy at AirGas told me all their grades of nitrogen come out of the same container. For the higher grades, they purge the receiving cylinder (as above, except they have about 2500 psi to work with..) The wasted purging gas, and the analysis and documentation, accounts for the higher cost.