Let me start by answering the short version of the question: Tor usually performs DNS requests using the exit node’s DNS server. Because Tor is TCP, it will only be able to handle TCP based DNS requests normally. Hidden services though are very different and rely on Hidden Service Directory Servers that do not use DNS at all. Read on if you don’t believe me or want more information.
Here’s a reference from an old mailing list entry:
Section 6.2 of the tor-spec.txt outlines the method for connecting to a specific host by name. Specifically, the Tor client creates a RELAY_BEGIN cell that includes the DNS host name. This is transported to the edge of a given circuit. The exit node at the end of the circuit does all of the heavy lifting, it performs the name resolution directly with the exit node’s system resolver. …For the purposes of DNS, it’s important to note that a node does not need to be marked as an exit in the network consensus to perform resolution services on behalf of a client. Any node that doesn’t have an exit policy of ‘reject *:*’ may be used for DNS resolution purposes. 
Pudding for the Proof:
Don’t believe me? Let’s test it out. If I run an exit node and then try to use it for a circuit, my DNS requests should go through it right? I’ve spun up an exit node named “BrianCranston” and I’ll setup a client (who I’m calling Aaron Paul) to only use this box as it’s exit node. You can do this by adding the following to your TORRC file:
And on my exit node, I do a tcpdump of all traffic on port 53. On my client I start looking for BrianCranston’s websites at briancranston.com and briancranston.org. Lets see what it looks like:
You’ll notice that Tor is being a little cheeky with the way it resolves DNS records. briancranston.org turns into bRiancRAnsTON.org.
I don’t know if this is just a nice way to let Exit Node operators know which hosts are being resolved by Tor or what. The reason for the odd casing in the DNS response is actually thanks to the Dan Kaminskys. Back in 2008, when exploiting DNS flaws was all the rage, one of the remediations for a DNS cache poisoning attack, was to randomize the casing of a DNS request. This was called the “0×20 hack” because if you look at an ASCII table of letters, you’ll notice that the difference between the letter A and the letter a, is 0×20. For example “a” is 0×61, and “A” is 0×41. The point here is that if someone wanted to attempt to pull off a cache poisoning attack, they’d have to brute force the possible case combinations. I’m told that modern browsers have this function built in now, but back in 2008, Tor was on the bleeding edge and its stayed in because it really doesn’t matter if a DNS query is 0×20′d multiple times. Thanks to Isis for pointing this out.
Tor is a TCP only network so what happens when it you need to use UDP services like DNS? The answer is pretty simple, it just doesn’t do it. Colin Mulliner and came up with a solution to this which was to relay UDP based DNS requests using a tool he wrote called TTDNS.(If you’ve ever used TAILS, this is what it uses.) In short, it takes a UDP based DNS query, converts it to TCP, sends it out over Tor, and converts the reply back to UDP once it’s been received.
Tor doesn’t natively support UDP based DNS queries, but Tor also only does two types of DNS queries: A records, and PTR records. It skips around needing to use CNAME by converting them to A records but officially, those are the only two supported.
There are a couple of other items to note related to DNS. One is that there is a built-in tool called “tor-resolve.” Guess what it does… make DNS queries over the Tor network. This is useful for command-line scripts that are trying to resolve a host.
The other, is a TORRC option that will open up a port to provide DNS resolution over Tor. Once enabled, you can use the local host as a DNS resolver on the port you specify. Again, this is how TAILS handles DNS resolution.
What about Hidden services?
This is fine and dandy to resolve google.com, but what about a hidden service with a .onion address. Connecting to google.com goes out an Exit Node, but connecting to an .onion address never leaves the Tor network. In fact, Tor doesn’t even use DNS to resolve .onion addresses at all. Here’s how that works.
The names generated for .onion addresses are not just random values unique to your host, they are a base32 encoded version of the public key associated to your hidden service. When you create a hidden service, you generate a priv/pub key pair. This .onion address, the port it’s listening on, some other useful classifiers, and a list of “rendezvous points” are published to Tor hidden service directory nodes. The rendezvous points are locations on the Tor network where a client can initiate a connection to the hidden service.
- Brian modifies the TORRC to offer a service on an IP address and port (127.0.0.1:443)
- Brian creates a keypair for the service and the .onion address is saved (briancranston.onion)
- Brian’s Tor client sends a RELAY_COMMAND_ESTABLISH_INTRO to start creating introduction points
- Brian’s client sends the descriptors (introduction points, port, etc) to the Hidden Service Directory Servers
- Brian then sends Aaron his .onion address (briancranson.onion)
- Aaron’s client checks the Hidden Service Directory Server to see if the address exists
- Aaron’s Tor client makes a circuit to one of the introduction points
- Aaron connects to the introduction point and tells it about his rendezvous point.
- This rendezvous point is passed to Brian
- Brian connects to Aaron’s rendezvous point
- The rendezvous point lets Aaron know that Brian’s service has been forwarded at that point
- Aaron finally makes a connection to Brian’s service
EDIT: Modified to differential between “rendezvous” and “introduction points” in the steps. Thanks to Isis for pointing that out.
So in short, hidden services are resolved using Hidden Server Directory Servers and the Tor client. There currently is no way (AFAIK) to manually just resolve onion addresses. That means, if you’re trying to connect to a hidden service using a script, you’ll have to properly tunnel the requests through Tor. That’ll be for another day.
If you need more information, check out these links:
http://archives.seul.org/or/talk/Jul-2010/msg00007.html - old mailing list message about DNS. A bit out dated but very useful
https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=rend-spec.txt - discusses the rendezvous protocol specification that is the basis of hidden services.