Well, I've run this gauntlet once, so I'll relate my experience. I moved from Vancouver, Canada (eh) to Houston, Tx (y'all) about three years ago.
On Getting a Job
IMO, you should not get a job through a headhunter. Sure, you might get lucky and snag a decent job, but from what friends have told me, almost all the jobs they have acquired using headhunters sucked. I managed to snag my current gig by hanging around on a Megadeth chat site. A couple of guys that work at my current job frequented the place, and one of them wrote the code for the site. He and I spent quite a bit of time geeking out, started swapping code, and eventually, they wanted to hire me.
I suppose there are other ways to network, like going to LUG meetings or conferences. Whatever vector you choose is probably unimportant. The important thing is that you actually get to know some of the yo-yos that you may potentially wind up working with/for. It will give you a much better feel for the environment in which you would be working. Turned out pretty well for me.
There's been many useful suggestions in this thread, so I'll only add one thing; if you find a job before you move, you can probably convince the company to expense your moving costs. With me, I was so damn broke (working at a university and paying school loans, and a few other things) that there was no way I could have moved all my junk down here without them paying. The only slight hitch was that if I bailed from the company before six months was up, I owed them the money they forked out to move me.
On Work Visas
For those of you planning to move to the States from either Canada or Mexico, here's the deal: If you are getting a computer related job, and you have a Comp Sci degree, you're in like Flint. To get a TN visa, all you need is to get a bunch of info about the company that is sponsoring you (get their lawyers to dig it all up and send it to you). Make sure your passport is in order. Get to customs/immigration whereever your point-of-entry is (either at the airport or the border crossing). Fill out a couple of forms, get your passport stamped. Budda-bing, you've got a TN visa.
I'm not entirely sure about H1 visas, but IIRC, you have to do a fair bit more legwork up-front to get them done. You can't just pick it up at the border.
As for H1 vs TN visas, an H1 visa lasts for three (I think) years, and can be renewed once. A TN visa is good for 1 year, and can be renewed (theoretically) indefinitely.
AFAICT, if you don't have a Comp Sci degree, or you job title doesnt exactly match the job titles listed in the INS regulations, you are shit-out-of-luck. Please correct me on that point if I'm wrong, because I've got a friend in Mexico that would like to take a sysadmin job here, but doesnt have a degree in Comp Sci. :)
Whelp, that's about it. Hope it helps.
/* The beatings will continue until morale improves */