Talk with your vet. You will need to get a hold of the USDA in your area. Your vet should have their number. You will need a health certificate from your vet, that you take to the USDA for them to review and emboss a 2nd health certificate from them. All shots will have to be up to date. The health certificate from the USDA is only good for a couple of days, so you need to have the fight booked and hope that all goes well and there are no weather delays.
Depending on where you are shipping, each country has different rules. I had one buyer from, I think it was Brazil, where I actually had to go in person to the Brazilian Counsolate for their signature. I could not fax it and the Counsulate was in Chicago and I live in Minnesota, a 8 hour drive one way. Needless to say, I did not sell that puppy to Brazil.
I have sold to England, Ireland, Switzerland, Austrailia and Singapore and did not have any trouble. I always used North West Airlines.