The creation of the hostname is described in rend-spec, 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 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?
Shallot is an example of a custom "vanity" address generator.