How do I change the IMEI of my iPhone?

This is not possible. Actually it would be possible in theory, but it doesn't help you in any way. A duplicate IMEI on the same carrier would automatically disable the phone by the carrier. It wouldn't help you to unlock it.

If you're asking this because you have stolen an iPhone, then this won't help you either, because there are other serial numbers that identify the phone and cannot get changed.
last edit: 2011-06-03

Most frequently read after this
Most read articles overall
Recently added or changed
 iPhoneiPod touchiPodiPad
 Apple TV 2GjailbreakunlockiOS 4.2.1
 Jailbreak FAQJailbreak F.A.Q.iPhone 3GApple
 mobile phonefirmwareiPhone 4iPhone 3GS