They 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.

[Shallot]: https://github.com/katmagic/Shallot

Shallot is run like this:

    $ ./shallot ^test
    ----------------------------------------------------------------
    Found matching pattern after 99133 tries: testvztz3tfoiofv.onion
    ----------------------------------------------------------------
    -----BEGIN RSA PRIVATE KEY-----
    MIICXgIBAAKBgQC3R85m6NQaA1ZjaYqvz1hvFIjbL4RtKdJbG8hlC9xEBkvfr/BG
    8Z5vDiUzdbDt8mEBuZUDanx80uGJvbXTgmczX0UlkEOgGiZ8RKpnsbKaf/EJNrIw
    T7MSXQmWNcm22nDeViV7fwy+Usyal2RE5cdVCFsPtEbVZqCumlKkEgCyFwIDBAZ7
    AoGBAJSa2cGuru/XhzJAEAIwHZbgPDnum9T/srOYxUKW6afHZeOu5S4Cclwb+xb/
    pGOtzn71XZfCKMfiVdxB/f3XTcRrYB2VnBoNToTD7WfH6DksdDf4zunqiEjvxi9K
    R+tKhxmF7OedrRt8wIhUmFd1E2Q9nbTHI6icdB4kR4QkYKZzAkEA5M6samK7+495
    6SWpRXiePIs7sHKWuxdCrG7kW5RNJrv2CcGYwK46TPcaXBcRfM4eq9+9PGoKi0IO
    gSpOZ5vRYQJBAM0QAZYTZ6ApD014x372MX1ZNofuYL/+XF8ZPZV6Sh4+9MUBuNPb
    yL7BENDr6pX4Zm6OepvAphhCa4vGno2pHncCQQCQnfhUCHANU4bjtX4EOoI63WDq
    UwBOeIWxu0YvGt7Z25Dg9CNz/aX8UZIoj6VyKxLRbR9+K3mNrNgaopW+ZDKzAkEA
    ttgTK1ALe+3v+5H+Ez1SvFPREDFcHihrfD1Ipc5zicY9ixTArgdyZvk+Pi+AMBVV
    sL2HWvjRLEAgRclvKfkwWwJAFtM+BIGRM5me+fMALuBBEtKnbJ6maflsyucErEb0
    pIIBkovF5oyWO3lSBmtStJIANNkHOg8aXqjcgPKusDN7CQ==
    -----END RSA PRIVATE KEY-----

By passing it a regular expression, you can describe what you want your .onion address to look like. Using this hostname and private key you can create the hostname and private_key files that tor expects to find in the hidden service directory.