Step 1) configure your zone(s) on the new server(s)
Step 2) update your configured dns servers at the domain registry (usually through an interface at your registrar)
Step 3) wait for as long as you feel is appropriate
Step 4) remove the zones from your old server(s)
Most tlds serve glue records with a ttl of 1-2 days. I'd wait at least that long after the tld servers update before dropping the zone on the old server. But you may want to wait much longer, because some DNS servers cache some records for an unreasonable amount of time. If you can change the NS records on the old servers to point at your new ones, that might help, but it might not. I don't know how much effort you want to put into keeping things working on servers that act unreasonable.
Thanks for the reply. That's roughly the strategy I'm thinking. In the past I would have also reduced the domain TTLs well in advance. You are probably correct about those using unreasonable TTLs on their nameservers.
That's going to make migrating name-servers painful. What a nightmare.
Edit: Just confirmed on my domains that moved. You cannot update the TTL of any record.
Can anyone suggest a strategy for safely migrating DNS providers without changing the current TTL settings since they can't be updated?