The best way is to apply for a skilled visa, which is what most people do. If your professional skills are in demand, it shouldn't be a problem getting a visa which allows you to work in Australia. Believe me, the working visa system in Australia is really good compared to the US. I've been through both and much prefer Australia's system although I'm not currently working there (would probably return someday).

State sponsorship is a good option. If you're going to be working in that state (find out if there are jobs there), then I don't think it's even an issue at all since you'll be living there while you work there. There are no restrictions on where you can travel, so you can still spend your weekends in other states if you wish to do so.