I moved my family to Austin first, without leaving my day job in ABQ. It is a big plus to have a local address, but I found that companies looking for talent did pay for plane trips, hotels and cars. However, these were the big companies, AMD and Freescale, et al. Smaller companies were not as willing to do so, and I think I got passed over several times for that rather than for my skills or lack thereof.

The thing that helped me the most was having a local contact in my skill arena who recommended me into a bunch of companies. Austin is very much like Hollywood in that everybody's a networker looking for mutual legs up. Wasn't even a previous friend, just somebody another friend suggested as a helpful person. Austin has a big (and proud) Linux geek community, so you might try a similar tack through that avenue.

Update: try Dice.com Metro Search also