Basically, you have to specially reprogram your new SIM's IMSI to match your AT&T SIM, essentially tricking your iPhone into thinking it's using the real deal SIM when it's actually on a different network entirely. Then, after a few (read: many) more steps and a sprinkling of fairy dust your iPhone could be carrier-free -- but with no guarantees data will work (since it's not like Apple gives you a place to configure your EDGE connection). In other words, caveat emptor, use at your own risk, and heed word to the wise: just wait for the real unlocking-hacks to be released. The iPhone's pretty good, but it's not good enough to jump through these kinds of hoops for no certain outcome.
That sounds more than a little risky, especially since I suspect that you'd invalidate any warranties or device support if you tried this.
Progress is being made on unlocking the baseband radio as the Baseband unlocking ideas page indicates. Ideas such as Dumping nvram, IMSI check trapping, Locating cyrptographic functions, Modifying onchip root certificate store, and SIM Proxies are all being explored.
I suspect we'll soon see unlocked iPhones for sale on eBay in the next few weeks.
What about you? Have any of you tried to unlock your iPhone? And if so, did you have any success?