Generally, the iceberg analogy, as applied to genealogy, refers to the fact that most records are not digitized and not online. However the "deep web" (as defined on the graphic in the question: information not accessible by surface web crawlers) for genealogy, includes
- records behind paywalls or requiring registration even to view
- dynamic webpages, created on the fly, from databases not directly accessible
- webpages not linked to anything else
- obscure sites (low ranking)
That means that, although Google may find the homepage of the site, it can't bring up many actual records.
I've noticed, however, that some sites (i.e. Findagrave.com) are becoming more directly accessible, possibly because of better linking of pages within the site, blog postings referencing pages within the sites (giving the searchbots a foothold within the site), or changes in the search engine algorithms.
In the meantime, the answer is to find the sites (by whatever means) and then, use the site's own search process, which is more versatile and tailored to the site, to access the actual information and records.
There are "helper" sites or applications, that can act as intermediaries:
To directly access deeper into genealogy websites:
- hints and search from within your genealogy software
- One-Step Webpages by Stephen P. Morse (uses usernames and passwords to the actual record providers to get access)
To supplement search engine indexing:
Your mileage may vary:
genealogy toolbars (too limited, in my opinion), example RelativelyCurious Toolbar
Mocavo - once free and focused on the world-wide web, now re-directs to FindMyPast and is focused on FindMyPast's collections, which are not free.