First, see the following:
APHIS:
http://www.aphis.usda.gov/animal_wel...t_travel.shtml http://www.aphis.usda.gov/NCIE/pet-info.html
The CDC website:
http://www.cdc.gov/ncidod/dq/animal.htm
You could also contact the veterinary authority in the state you are moving to, in case there are further state requirements:
http://www.aphis.usda.gov/vs/sregs/
(Bear in mind that Hawaii has special quarantine rules.)
Some airlines require a 'fitness to fly' certificate from your vet, or other form of liability waiver. Contact your airline for exact requirements/restrictions. Also bear in mind, some airlines/airports suspend animal travel during the summer months because it is too dangerous in the heat.
Some airlines have a limited number of pet spaces per flight, or restrictions on how far in advance you can book the pet's travel.
Generally, dogs under 6kg (including the container weight) might be allowed to fly in the cabin, larger dogs usually will have to go in the cargo hold. Airline requirements for the travel crate vary, check your airline's policy in advance.
And it is best to fly your pets on direct flights whenever possible.
MusicOfNote, my dogs have flown around the world several times, always in the cargo area. It's not something I would ever consider doing for a short vacation, but they survived the flights surprisingly well.
The first time, I was lucky enough to have a few weeks notice before moving so I had time to acclimate the dogs to their travel crates and teach them to drink from the drip bottle - this is very important. I put something of mine in the crate - usually a used t-shirt - and a favorite toy so that there is something to comfort them during the trip. (Note - I know of one case where the owner was not allowed to put any stuffed toys or padded bedding in the crate because US customs was concerned that such things were used for drug smuggling - but I've never had any trouble doing so. Of course if your dog chews or destroys toys do not put one in, as the dog could accidentally choke.) I fit the crates out with a drip bottle over door mounted bowl - freeze the bottle - as the water melts during the trip the dog has enough to drink, and less chance of spillage.
I want my dogs to travel together in adjoining crate spaces so that usually means booking well ahead. One of my dogs is insane around cats, so I try to book on flights where no cats are traveling.
The longest flight leg my dogs have done was about 11 hours. If longer than that, I have to stop midway in order to give their poor kidneys a break - but you should plan very carefully when you do something other than a direct flight.
I prefer to use an animal shipping expert to plan and co-ordinate my mutts' travel. Well worth the added expense, IME.
For a list of IPATA members, see:
http://ipata.com/