It says that Sauron waited over a thousand years or more laying dormant regaining his strength after being destroyed when his ring was severed from him. But does the text say how he actually recovers strength?
The texts don't say precisely how this happens, but it's worth noting that this is not the first time that Sauron has had to rebuild himself after physical destruction.
In some versions of the stories Sauron was "killed" (i.e physically destroyed) after his encounter with Beren and Lúthien.
And, of course, he was also physically destroyed at the Fall of Númenor.
One point to note is that physical destruction for one of the Ainur (even a lesser one like Sauron) is not such a huge impediment, as the Ainulindale notes:
Moreover their shape comes of their knowledge of the visible World, rather than of the World itself; and they need it not, save only as we use raiment, and yet we may be naked and suffer no loss of our being.
It's also important that as one descends into evil, one will lose this ability. Melkor/Morgoth lost the ability after his destruction of the Trees, and it may be assumed (although it's not certain) that Sauron lost it after the Fall of Númenor.
Beyond that we're left with speculation.
The Ainur are capable of taking form commensurate with their inherent spiritual power, which is why the forms the Valar were capable of taking were more gigantic. If they become dependent on that form and then lose it, they have to invest more and more of their personal "spiritual" energy into sustaining it, or building another.
In Morgoth's case this is made explicit with the so-called "Melkor ingredient" or element mentioned in Morgoth's Ring, which is explicitly tied to the process behind Sauron's Ring (which he used to sustain and rebuild his physical form so quickly after the fall of Numenor, hence why he was less able to re-embody after the Last Alliance because he had used his power in the Ring to re-embody himself more quickly.)
It all ties into Tolkien's idea of "good" (spiritual) "magic" which is invested in potential energy (preservation, understanding) vs. (physical) "sorcery" which is invested in "decreasing the distance between thought and [physical] effect" as Tolkien put it (paraphrasing). Think of it as turning potential (spiritual) energy into kinetic energy (creating a body), which is an enthalpic process just as it is in nature (decrease in entropy to form a complex structure, thus requiring more of the user's essence).
Morgoth expended too much of his energy on destroying other people's things, and Sauron spent his trying to control and hence concentrate the energy of others, again an enthalpic process ("for the Elven Rings were powerful and the power needed to control them must be equally great", again paraphrasing). The "natural" bodies of the Ainur required less energy to create for they were less physical constructs and more mental.
Sauron (and Melkor) wanted a physical construct, the better to rule over his subjects. Gandalf's body was not only physical but biologically human (incarnate), so required outside influence by the higher Powers to sustain if "broken".
On Edit: Tolkien quote from the other answer providing more evidence for my claim:
After the battle with Gilgalad and Elendil, Sauron took a long while to re-build, longer than he had done after the Downfall of Númenor (I suppose because each building-up used up some of the inherent energy of the spirit, which might be called the 'will' or the effective link between the indestructible mind and being and the realization of its imagination). The impossibility of re-building after the destruction of the Ring, is sufficiently clear 'mythologically' in the present book.
Note that this is actually a restatement by Tolkien of his entropy / causality theory for "magic" and "spiritual power" about "shortening the distance between cause and effect", the one which I mentioned earlier I believe is in the letter to Milton Waldman.
I think he came to power again like a parasite, I think he fed off of negative energy that the corruption the ring brought about in its wearer.
there is precedent for the mair/valar being reduced from the spiritual to the physical (morgoth), and being subject to physical limitations (thorondor left a scar on morgoth's face, and fingolfin cut off (or wounded) his foot)...it also seems to be implied (and i believe explicitly stated) that morgoth was limited to a body after his evil (much like after the fall of numenore, sauron could never again resume his fair form). furthermore, it is speculated on 'morgoth's ring" (book X) that morgoth surrendered much of his 'force' in marring the earth, much like sauron did with the rings. perhaps as an author, tolkien was saying that evil deeds weaken to doer. men can be slain and go to parts unknown...elves' bodies can be slain, and their fea go to mandos, where they mayhap be rehoused...perhaps the 'life' of a maia is different. gandalf (of sauron's "order") "died" and was rehoused (by the valar?), but enhanced. saruman "died" and his energy was dissipated. sauron "died" at numenor, but he left part of his life energy in the Ring, like a bank account. that bank account does not preserve ALL of his holdings, and when the ring was cut from his hand, he lost his atm card (ie, the ability to wield his power directly). i also agree with user33157...evil has a parasitic way of finding power (especially since the ring was not destroyed (his bank account still earning interest).