Adding private keys is the same as point addition for public keys.

For vanity addresses, I generate pri1 and corresponding pub1. I provide pub1 to the vanity address search service. The service searches for a pri2 such that pub1+pub2 is an address that has the right prefix. Pri2 is returned to the requester.