To disappear so completely that nothing but empty air is left.
--History--
I'm going to predate Shakespeare by referencing Virgil's Aeneid (30-19 B.C.). By 1490, William Caxton had translated it into English under the title Caxton's Eneydos. This is roughly 120 years before the publication of The Tempest, and it had already been translated into Italian and French by the time Caxton translated it. According to Terrance Cave:
Much more complicated, and more interesting, is the case of The Tempest. Scholars, following the lead of Donna Hamilton, increasingly present the play as a sustained imitatio of the Aeneid.
Terence Cave, Recognitions: A Study in Poetics (Oxford 1990), p. 289
While I can't find a handy online copy of that book, it's also educational to read Charles Martindale, who quoted Cave in his own work Shakespeare and the Classics. It's worth keeping in mind that Shakespeare would've studied Latin, so it is likely that between English and Latin he had read the Aeneid.
--Phrase--
So with the interesting history out of the way, let's look at this interpretation of the phrase. We will use this 1791 translation of the Aeneid, because it is keyword searchable. While this copy is from ~180 years after The Tempest, other translations (and the original Latin) predating the Tempest likely are along the same lines. The phrase "vanished into thin air" appears a few times (p. 139, 170, 199, 306). However, the most compelling evidence for my argument is on page 90:
...and on a sudden fled from his fight a different way, like smoke blending with thin air..
So disappearing as if he were smoke dissipating and leaving no trace that he had been there.