ThePiachu explains it like this:
The idea is, that you can generate a vanity address without even
knowing what private key it will actually belong to. One party grabs a
random ECDSA keypair and saves the private key for themselves. They
later can issue a request for a vanity address to be created, by
supplying the public key form that keypair, their desired pattern and
so forth. A person takes with looking for the vanity address is
required to brute force random ECDSA private keys, get their
corresponding public keys, add them to the provided public key, and
proceed normally with SHA, RIPEMD and base58 until they receive the
desired pattern. Then they give the private key they found to the
first person, which adds the two private keys in order to get their
vanity address. The best thing about it - the person looking for the
solution won't know what the resulting private key is! This means that
you can outsource your vanity key generation without needing to trust
any third party.
An example (available from gobittest website): We have a private key:
18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725 which
maps to public key:
0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A
299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6
and say we want to find a pattern "166". One of the solutions takes a
form of a private key
B18427B169E86DE681A1A62588E1D02AE4A7E83C1B413849989A76282A7B562F
mapping to public key:
049C95E0949E397FACCECF0FE8EAD247E6FD082717E4A4A876049FB34A9ADED110DFEA2EF691CC4
A1410498F4C312F3A94318CD5B6F0E8E92051064876751C8404
If we add the two public keys (like the person looking for the
solution would do), we get a public key:
0436970CE32E14DC06AC50217CDCF53E628B32810707080D6848D9C8D4BE9FE461E100E705CCA98
54436A1283210CCEFBB6B16CB9A86B009488922A8F302A27487 which is
equivalent to this address: 166ev9JXn2rFqiPSQAwM7qJYpNL1JrNf3h
If we add the two private keys (like the person requesting the address
would), we get:
CA65722CD418ED28EC369E36CFE3B7F3CC1CD035BFBF6469CE759FCA30AD6D54 which
maps to the same public key as the sum of the public keys, and thus -
to the same address.
Since this is a model that requires basically no trust from any party,
I've decided to create this "Vanity Pool" to enable people to easily
outsource their vanity address creation, as well as enable people
wanting to earn some Bitcoins to use their machines for something
different from traditional mining.
The simplest option to get the keypair to get started with the vanitypool is to go to https://www.bitaddress.org/ and generate a new address. Note down the private key. Now switch the tab to "Wallet Details" and enter the private key. One of the resulting fields is the "Public Key (130 characters [0-9A-F])" which has exactly the required format that is needed for the vanity pool.
Once a solution is found just combine the result that is mailed to you with the private key you noted before and you can import it into your Bitcoin client.
