The way I do it is:
1. Upload everything to your new host
The next steps assume you use windows, I'm sure there are analogous steps for other OS'es but I'll neglect them for shortness
2. Open C:\WINDOWS\system32\drivers\etc\HOSTS with a text file
Add an entry like this:
Code:
1.2.3.4 yourDomainName.com
where 1.2.3.4 is your new host's IP
What this does is tells windows to resolve yourDomainName.com to 1.2.3.4 for the life of that entry. This allows you to test your new host like it was on the actual domain.
3. Go to yourDomainName.com and test that everything is working fine. Now you can remove the entry you added in step 2
4. Change your nameservers to your new host, BUT don't cancel your old hosting account just yet. Wait at least 2 days before cancelling it.
5. That's it, if all went well, you should experience no downtime at all.
If you're wondering about the technicalities of it, the reason is because while your DNS is propogating (big word for being updated around the internet), you're leaving the old IP intact, as well as the new IP, so even if some people's DNS records aren't updated, they still won't notice a thing because they'll be going to your old host.
I hope that helps