We've moved from AR to LA, and then from LA to FL (plus intercontinental moves, but thats not exactly the same). What I've done is:
(1) Line up a job ahead of time
(2) Identify a cheap motel near the job & book there for a week
(3) Use zillow & other websites to look for rental places that fit my needs, a week before moving, and contact the agents/landlord to go and see them immediately after the move
(4) Pack all our shit into a Uhaul truck and drive - cats go into cages in the car which gets driven behind the truck (or on a car-trailer if you need to).
(5) Store the Uhaul truck at Uhaul while you're at the motel, then once you have a rental, unpack into it.