The Deep Web is "simply" all the pages that are not indexed by search engines.
The search engines like Google get from one page to another by following links. Any page that is not being linked to would belong to the Deep Web, unless someone submits it to a search engine. The phrase "deep web" sounds mysterious but in fact we all use it to an extent. If you are on a password protected site like Monster or Dice, you are using the deep web. If you run a database query somewhere on the web, and get a dynamically generated page, you are on the deep web.

Here are a few pages with definitions and overviews.
http://en.wikipedia.org/wiki/Deep_web
http://www.internettutorials.net/deepweb.html
http://www.lib.berkeley.edu/TeachingLib/Guides/Internet/InvisibleWe...

The deep web sounds exciting since its size is way, way bigger than the total size of indexed pages.
Have you used the Deep Web in your sourcing? Would you have some good sites / hints to share?