There are at least 3 ways:
- Links to your site.
- Using Google Webmaster Tools (now called Search Console)
- Registrar dumps, triggers, and other options.
Google will find many new sites quickly from some registrars. For example, Google found one domain name I registered using GoDaddy, indexed it, and began sending search results within 20 minutes of registering the domain name. But this will not happen for all registrars.
There may be other ways as well, but these are the most common.
If you want Google to know about your site quickly, the best option is to submit it using Google Webmaster Tools (now called Search Console).
@zigojacko brought up a great point(!) in the comments that really should live within the answer. If you have a Google+ account, you can simply link to your website and Google will honor that immediately. It is at least as fast as creating a WMT account if not faster!
[Hint]
Sitemaps and robots.txt files have nothing to do with domain discovery. In fact, sitemaps are useless for most sites with the exception of extremely large sites, sites that cannot be crawled completely because not all pages are linked, sites with a paywall, or sites with a login. Sitemaps have nothing to do with search performance short of the reasons mentioned above. As well, it is always advisable to create a robots.txt file even if it is empty.