I heard this expression during the broadcast of a baseball game during which a team was described to have “manufactured a run out of thin air.” Apparently that is an unusual use of the expression, which has more commonly been used to describe magic tricks that appear to make things appear or disappear without a trace or explanation. The FreeDictionary.com has the best explanation for the use by the baseball announcer, saying it means “…out of nowhere, out of nothing…” It gives the example of “You just made that excuse up out of thin air.” According to the Phrase Finder Shakespeare started the overall use of the expression in 1604 by having a character describe how something would “…vanish into air…”