So you would need both private keys to spend the coins from that address?
Correct - basically some clever math stuff is involved which makes it safe for you to get someone else to generate your vanity address.
There is a service offering to do this (not free except for easy ones) - if you search the forum it should be easy enough to find.