How do you discover the size of a potential market?

The absolute best way to do it is likely untenable - through a statistically valid research survey by a professional surveying company. We've participated in one of these at SEOmoz, but luckily, the majority of the cost was picked up by a much larger enterprise.

Next best is likely a combination of search demand and competitive analysis + data from third party data/research firms like Forrester/eMarketer/etc. I'd guess that many articles written about Ancestry.com include some mention of this. For the self-generated portions (search demand and competitive traffic numbers), you can use www.google.com/sktool and www.google.com/trends to get some insight. Remember that with Google Trends, you'll want to be logged in to your Google account to see real numbers.

I would start with the public numbers around competing sites like Ancestry.com, FamilyTree.com, as those would be the closest to your market. You can use sites like Quantcast, Compete.com, etc to estimate the number of unique visitors these sites are getting.

Ancestry.com brags that they have almost 1 million subscribers (which means > 500k)[1]

You could probably also find readership numbers for magazines focused in your industry, most of them will include the numbers in their media kit, or if you request advertising information they should provide them. [2]

I'd dig into your closest large competitors and work out what their revenues and users are. compete and financial data will give you a good record, and don't forget to network via linkedin and ask them outright.

The other thing to do is to talk to people that are clever. A VC is trained to know large and small markets, for example. Business professors, MBAs and so on generally have a great "guesstimate" of this stuff. Thats what we did.

Look around for numbers. They pop up every so often.

e.g. Here's a good one to help determine market potential from Ancestry.com's Genealogical Juggernaut, by Bruce Falconer on Sept 20, 2012:

Today, genealogy ranks second only to porn as the most searched topic online. According to a January 2012 report by market research firm Global Industry Analysts, an estimated 84 million people around the world spend anywhere from $1,000 to $18,000 a year in search of their ancestors.