Thy use a tool like Shallot to brute force the onion address
What Shallot does is to generate a private key in the same way that the Tor software does when generating a new hidden service address. It then manipulates the public key portion of the key to create new versions of the .onion address and checks through those to see if they match the desired address.
It generates a new private key periodically. The keys generated by Shallot and other methods of brute forcing an onion address have a larger than average public key component but are syntactically fine and pass all tests ensuring that they are good keys.