First you will need a sim card from a different carrier.
Request your sim unlock code from your carrier or as an alternative you can go to Ebay (this vendor fonecare was great, cheap and super fast, got my code within minutes for less than $5 but there are many others). In both cases you will of course need to provide your IMEI number (*#06#)
Here is the BIG ONE: You need to be on a stock rom! All attempts to sim unlock on a custom rom (cm, aokp, etc..) will result in a message telling you the "sim unlock attempt was unsuccessful". After 5 unsuccessful attempts you will "permanently" lock your phone (Well not so permanently as you can reset the counter by running an RUU, but it's PITA...) If you're indeed on a custom rom (if you're not I don't really know what you're doing on xda?!) read the following:
Make an nandroid backup of your current setup with your recovery of choice.
Push a "stock rom" to your SD card, I used the latest 3.18 since AT&T is my network here but you can also refer to @redpoint73 exhaustive index for a list of all the stock rooted roms available for the Evita here
You may or may not have to flash a radio depending of whether your "stock rom" of choice comes with it or not. If needed go to @taylor.fowler thread on radio here, pick the matching radio and push it to your SD card
Reboot in Recovery
Wipe cache & Dalvik and Factory Reset.
Flash the "stock rom" you moved to your SD card (as well as the radio if needed.)
Wipe cache&dalvik again (don't really know if it's necessary, i think the jury is still out on this matter but it doesn't hurt)
Reboot to your "stock rom" to make sure everything is fine and dandy
Remove your current network sim card and replace it with another carrier sim card (this will trigger sim unlock prompt once you're rebooted)
Turn your device on
You should be prompted for sim unlock (not to be confused with sim pin which some carriers require before you get to the sim unlock prompt)
Enter your sim unlock code and hit "ok", should be followed by a "sim unlock request successful" et voilą
Reboot in recovery, again wipe cache&dalvik, factory reset and restore your nandroid backup. Amen