TranscendLinux.com

Short version
1) Lower TTLs (allow 48-72 hours for propagation)
2) If migrating to new DNS servers, configure DNS on the new DNS servers
3) Verify functionality of migration server
4) Point DNS at migration server

Longer version
The first step in DNS migration is to lower the TTLs on the current nameservers. If migrating to new nameservers, then this is also the time you'll want to configure the appropriate DNS entries there. You will also wish to verify that all content and services are running properly on the new server (you may need to configure /etc/hosts entries to verify the functionality of name-based virtual hosts in Apache).

Allow a minimum of 24 hours to pass to allow propagation of the TTL changes, and then point repoint DNS as needed. If migrating nameservers as well, you'll also change the nameservers associated with the domain at the registrar (it's advisable to do both when migrating nameservers, as this will ensure the minimum service interruption in the case of slow propagation, and in case the old nameservers get queried).

Stealth migration
1) Recreate existing DNS records on the new provider's nameservers
2) Lower TTLs on new nameservers
3) Change nameservers to the new provider's at the registrar
4) Allow 48-72 hours for propagation
5) Change the DNS records on the new nameservers to point to the new provider's servers

If migrating from one provider to another, it is often handy to do so with minimal notice to the provider you are leaving. If you control your own DNS, then this is easy, however if your hosting provider controls it, you need to be "stealthy" about the process. This procedure will allow you to migrate from one host to another without any notification to the current provider (assuming they are not also the registrar for any pertinent domain names).

The first step is to retrieve as much information as you can about the existing DNS setup without contacting the current provider, and recreate your DNS configuration on the new nameservers (still pointing to the old provider's servers). You should also lower the TTLs on those domains to 5 minutes.

The next step is to change the nameservers at the registrar to the new nameservers. There should be no service interruption here, as the zone files on both sets of nameservers should be identical. After allowing 48-72 hours for this change to fully propagate, you may change the DNS records on the new nameservers to point to the new provider's servers, at which point you should be all set!