First, ask the root servers for the authoritative servers for the TLD you are interested in:
$ dig @f.root-servers.net www.google.com
[...]
;; WARNING: recursion requested but not available
;; QUESTION SECTION:
;www.google.com. IN A
;; AUTHORITY SECTION:
com. 172800 IN NS a.gtld-servers.net.
com. 172800 IN NS b.gtld-servers.net.
[...]
com. 172800 IN NS m.gtld-servers.net.
;; ADDITIONAL SECTION:
a.gtld-servers.net. 172800 IN A 192.5.6.30
b.gtld-servers.net. 172800 IN A 192.33.14.30
[...]
m.gtld-servers.net. 172800 IN A 192.55.83.30
a.gtld-servers.net. 172800 IN AAAA 2001:503:a83e::2:30
[...]
The root servers don't know about google.com, but suggest you ask
[a-m].gtld-servers.net, which are authoritative for .com. (Other TLDs have
other authoritative servers.) So let's ask l.gtld-servers.net: $ dig @l.gtld-servers.net www.google.com
[...]
;; WARNING: recursion requested but not available
;; QUESTION SECTION:
;www.google.com. IN A
;; AUTHORITY SECTION:
google.com. 172800 IN NS ns2.google.com.
google.com. 172800 IN NS ns1.google.com.
google.com. 172800 IN NS ns3.google.com.
google.com. 172800 IN NS ns4.google.com.
;; ADDITIONAL SECTION:
ns2.google.com. 172800 IN A 216.239.34.10
[...]
ns4.google.com. 172800 IN A 216.239.38.10
[...]
The above is an example of a registered domain ("I don't know about
www.google.com, ask ns[1-4].google.com"); if the domain is not registered, it
looks like this: $ dig @l.gtld-servers.net no-such-domain.com
[...]
;; WARNING: recursion requested but not available
;; QUESTION SECTION:
;no-such-domain.com. IN A
;; AUTHORITY SECTION:
com. 900 IN SOA a.gtld-servers.net. nstld.verisign-grs.com. 1301905185 1800 900 604800 86400
[...]
Of course, [a-m].gtld-servers.net are run by Verisign, who could use this information for front-running. I'd be very surprised if they did, though. (DNSSEC may make it possible to query for the existence of a name without revealing it to the answering server, but I'm not sure - I'd have to read up on the protocol.)