Though they resolutely refuse to talk about it in public, because IMEI spoofing is illegal in the U.S. and most other countries, experts on smartphone jailbreak forums treat changing IMEIs as only a moderately interesting configuration process.
There are a number of Java scripts and apps for both Windows and MacOS designed to change out the IMEI, often as only one of a wider range of features to root the phones, create a backup image and change out portions of the operating system.
Some emulators are able to send fake IMEI numbers to the carrier's network, even without changing the IMEI on the phone itself. They spoof by replacing a number you choose with the real one, and return the phone to normal when they're shut down.
The easiest way
There's an app for it.
In fact, there are a lot. Most are designed to test applications that have to identify multiple IMEIs, or to recover an IMEI when an attempt to root or re-flash the phone bricks it instead. Many can be used to emulate phones with other IMEIs as well.
The stupidly easy way
If your victim's phone supports Bluetooth and he/she has Bluetooth turned on, you can connect to the phone directly. Once you make the link, there are any number of (also illegal) tools to pick up the phone's ID, copy the contacts or voicemails already on the phone and sometimes change the victim's password as well.
If you have a good idea what the password is, or know the victim's username and are willing to use the Change Password function on the cell phone carrier's voice-mail access page on the Web site, you can skip all the rest and just do that.
It's a lot easier to lie to one web app than it is to figure out what lie you have to tell and then tell it in the right format to your phone, a whole cell phone network and then to the voice mail server.
See? Easy. If you're into that kind of thing.