The creation of the hostname is described in [rend-spec][1], the Tor Rendezvous Specification. 

You are 100% correct: There is *no* central domain name provider on the Tor network. There is *no* central *anything* provider on the Tor network. 

###How it works: 

Tor generates two keys for every service on the Tor network. Tor generates a private "secret" key, and a public "address" key. These work a little like the email-password(sort of like the private key) and email-address(sort of like the public key) combination we're familiar with. 

The .onion public "address" domain name is built from the shorter, public key of the service. 

First the public "address" key gets hashed with SHA-1. 

The first 80 bits of the output are encoded with Base32 (see [RFC 4648][2] for a description). 

The result is the hostname of your hidden service.

The Tor software handles this generation for servers. 

###Further Reading / Try it out

For a more custom "vanity" .onion address generator, some have maintained services like those mentioned here: [How do Hidden Services get .onion domains that aren't random?][3]

[Shallot][4] is an example of a custom "vanity" address generator. 

  [1]: https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=rend-spec.txt
  [2]: https://tools.ietf.org/html/rfc4648
  [3]: https://tor.stackexchange.com/questions/10/how-do-hidden-services-get-onion-domains-that-arent-random
  [4]: https://github.com/katmagic/Shallot