The most populous subclass of stringy vacua are type IIB flux vacua - studied in the KKLT paper. To find one such a vacuum solution of string theory, you need to specify the topology of a Calabi-Yau 3-fold, or 4-fold. There are just thousands of topologies.
However, for each topology, you will find something like hundreds of cycles in the homology, and each cycle may carry a certain integer number of units of the generalized magnetic flux (the integral of the $p$-forms describing a magnetic flux from the Ramond-Ramond sector, besides the 3-form H-field from the NS-NS sector). There exists an inequality implying that these integers can't be arbitrarily high.
If you have hundreds of cycles and each of them may have something like 10 different values of the flux, the number of discretely different possibilities will be like $10^{hundreds}$. For each choice of the integers, you may find a rather small number of solutions for all the shapes so that the potentials are minimized etc. So one gets an googol-like number of configurations of the RR fluxes; more precisely, this is a large number of supersymmetric AdS vacua (with a negative cosmological constant). It is believed that each of them may be dragged above zero to obtain a non-supersymmetric de Sitter background (which is needed) but there's no completely strict proof that the number of metastable de Sitter vacua is huge as well. The supersymmetric vacua are much more controllable.
The original "modern" vague claim that the number of vacua is a googol or its power was written down by Bousso and Polchinski in 2000:
http://arxiv.org/abs/hep-th/0004134
You won't find the specific number $10^{500}$ over there which, I think, first appeared in a paper by Douglas. Douglas has made interesting fancy mathematical contributions to the counting of the vacua but I wouldn't count the "fashionable" value of the estimate to be among his major contributions. Search for 500 and references 8,9,10,11 or so e.g. in this paper:
http://arxiv.org/abs/hep-th/0411173
You will find a link to the KKLT paper, and others.
One has to mention that there is nothing truly original about these "large" estimates. Wolfgang Lerche claimed that the number of certain vacuum solutions to string theory equations was something like $10^{1500}$ back in the 1980s.
Many other important phenomenological classes of string vacua are still thought to be vastly smaller. It is both good news and bad news. It is good news because you might think that they're much more unique and predictive. It is bad news because no one knows a convincing reason why these vacua should be able to produce the tiny observed value of the cosmological constant.