This is a standard statistical problem.  It goes under a number of names, which is probably why you haven't been able to find it by Googling.  In ecology, it's called "estimating species richness", and in computer science it's called "stream estimates for $L_0$.".  The classic solution is [Good–Turing frequency estimation][1], which was developed during the second World War.  It's still good enough for many practical purposes.  I'd start by reading about that, and if that's not good enough for your application, following the literature forward from there.

Arthur B is right that you can do it using MCMC.  But that's using a bulldozer to pluck a flower.  It works, but MCMC is really meant for much harder jobs.


  [1]: http://en.wikipedia.org/wiki/Good%25E2%2580%2593Turing_frequency_estimation