Assuming you have control of your individual DNS records:
If you do not have a database or files that are being modified by visitors to the site (new users created etc):
- set up new hosting with new provider (just purchase hosting only, not hosting plus domain - make sure the hosting is configured to use your main domain name though)
- copy the website + database over to the new hosting and change any settings that need changing for the new server (the website might be using absolute paths somewhere...)
- test the site; often your hosting provider will give you a 'temporary' URL (ie, URL alternative to the main domain name), else you can modify the hosts file on your computer to point the domain name to the new hosting IP
- when tested ok, modify DNS to point website to new hosting server (if you want to transfer the domain name to the new provider - which is not necessary btw - then change the name servers at this point to the new providers name servers)
- if you do want to transfer the domain, kick it off a few days later. the name servers should already be pointing at the new hosting providers servers
There should be no downtime with this method if you do it properly.
If you do have database/files that need to be kept current:
- do points 1-3 as above
- as ampere has said, set up a subdomain on your new host, pointing into the same folder as the normal www (say, new.mydomain.com)
- add the subdomain to your DNS
- wait a few days
- put a temporary holding page up on your old host
- quickly update the database / any changed files on your new host with whatever has changed since point 1
- on the old host, replace the holding page with a redirection to new.mydomain.com (which will have already propagated, pointing to the new server)
- wait a few days
- change your name servers to the new host (by this time you can get rid of the new subdomain as everyone should be using the www to come to the new host, or you can keep it and set up a 301 redirection to www if you're worried about any links/SEO issues with the temporary subdomain)
- transfer the domain to the new host
The downtime involved here is however long it takes you to do points 5-7.
Sadly, both take up a fair bit of time, and what you are able to do depends on what services your hosting provider gives you. Some will not give you individual DNS control, some will not let you direct a subdomain into the main website document root etc. If you have flexible hosting providers + use a separate domain registrar (so you don't need to transfer the domain as well) then you can do a lot more to mitigate transfer downtime.