Not sure if this still stands true, but here is a clip from the sulcata-station.org
"What to do if you are transporting a Sulcata Tortoise across state lines within the United States
As currently written, the federal regulation does NOT distinguish between captive-bred tortoises that have never left the United States and the wild-caught imported tortoises that carried exotic ticks into the U.S. Because of this, we recommend that you obey the federal regulation -- not only because of the possible health consequences to native wildlife, but to avoid having your tortoise confiscated if you happen to encounter a USDA inspector who is familiar with this regulation.
If you plan to travel with your tortoise, or if you plan to ship a tortoise to an adoptive owner in another state, you should follow these procedures:
At least one week before your travel/shipping date, have an accredited veterinarian examine the tortoise. The vet should provide a basic checkup and visually examine the tortoise closely for ticks.
If no ticks are found on the tortoise, the veterinarian should sign a Certificate of Veterinary Inspection or similar certificate (the vet's office should have these on hand) stating that the tortoise is tick-free. You will have to pay for the office visit and the inspection certificate.
Make sure a copy of the Certificate accompanies the tortoise at all times. Tape it to the shipping container, or make sure it is kept on hand by the person transporting the tortoise.
State Regulations
Unfortunately, there is no single source or website that lists all of the states' rules about exotic pets. You may have to do a bit of searching on the internet or call various agencies to find out what rules apply in whatever state you're relocating to. Generally, these laws are administered by the state's Department of Wildlife, Dept. of Natural Resources, Dept. of Game and Fish, or the equivalent. In some cases, you may even need to check with the state's Health Department!"