Solution 1:

Your computer has a list of DNS servers that it can query for further information. On a unix or linux system, this is stored in /etc/resolv.conf. In Windows, it's configurable in your network settings. Often, your DNS server will be supplied by your DHCP server, possibly along with other settings like default domain, proxy servers, etc.

The location of the DNS server you use doesn't matter much. As long as your computer has an IP address and a working default route (i.e. you can ping the DNS server), you should be able to make DNS queries.

DNS servers don't have to know "all" domains. They only need to know who is "authoritative", which it learns from a set of "root" servers. Each DNS server has a list of "root" servers, and this list changes infrequently. On one of my DNS servers, there are 18 root servers configured, and this configuration came when I installed the DNS server two years ago, and if the list of root servers has changed since then, enough of them are accessible that I haven't noticed it.

My DNS server, when asked to resolve a domain it doesn't know, makes a query to a root server to find out what other DNS server is authoritative for the domain. The response it gets may contain additional "NS" records and be marked non-authoritative, in which case my DNS server knows that it has to "follow the chain" and make a new query to a new server. Eventually, it finds a DNS server that provides authoritative information, and queries can be made that are not just NS records. A (address) and MX (mail exchange) are of course the two most common.

Each TLD (top-level domain) like COM, NET, ORG, CA, UK, etc maintains its own registry of subdomains. (A "subdomain" is any domain within another domain, so "example.com" is a subdomain within "com", and "com" is even a subdomain within ".", the "root".) The rules for each registry apply only to the TLD it administers -- that is, there's a completely different set of criteria for each country-code TLD, and the "generic" TLDs are administered by different organizations with different policies. But they all maintain DNS servers for their TLD, which, from a command line, you can see using basic DNS query tools:

[ghoti@pc ~]$ host -t ns ca.
ca name server c.ca-servers.ca.
ca name server e.ca-servers.ca.
ca name server z.ca-servers.ca.
ca name server a.ca-servers.ca.
ca name server f.ca-servers.ca.
ca name server sns-pb.isc.org.
ca name server j.ca-servers.ca.
ca name server k.ca-servers.ca.
ca name server tld.isc-sns.net.
ca name server l.ca-servers.ca.
[ghoti@pc ~]$ host -t ns info
info name server c0.info.afilias-nst.info.
info name server d0.info.afilias-nst.org.
info name server b2.info.afilias-nst.org.
info name server b0.info.afilias-nst.org.
info name server a2.info.afilias-nst.info.
info name server a0.info.afilias-nst.info.
[ghoti@pc ~]$ 

When you buy a domain from a registrar (of which there are many), that registrar submits information about the domain to the registry (of which there is just one per TLD). It is the responsibility of each registry to maintain the list of registered domains within their TLD, and maintain the DNS servers that provide this info to other servers.