If having very small downtime is an issue, and you have a very active database, you may want to consider setting up the new server to slave off the old server. Follow the MySQL replication documentation, setting up the new server as a slave. Then, when you are ready to make the change, you just start having your applications access the new server instead of the old -- perhaps by bringing the IP address down on one and up on the other, reconfiguring your application to the the new server address, etc...
However, this is usually overkill for most sites. Usually you can take a few minutes of downtime to do the move, using a mechanism such as what follows...
Start with just priming the copy while MySQL is running on the source server (and down on the destination), with something like:
rsync -avzP --delete /var/lib/mysql/ root@destination:/var/lib/mysql.source/
I run it to a destination of "mysql.source" so that I can be sure that if I make a mistake I'm not, say, overwriting the active server with data from the new server. Depending on the speed of the network, this may take a long time (say, if you are moving from one provider to another over a 1mbps link).
Once this finishes, run it again to transfer the changed files. This should be dramatically faster.
After re-running it a few times, it will probably get down to something very small, maybe a few seconds.
At this point, you are ready for the final rsync. To do that:
ON OLD SERVER:
/etc/init.d/mysql stop
rsync -avzP --delete /var/lib/mysql/ root@destination:/var/lib/mysql.source/
ON NEW SERVER:
cd /var/lib
mv mysql mysql.orig
mv mysql.source mysql
/etc/init.d/mysql start
Of course, this assumes that you have already copied over your my.cnf and made appropriate adjustments if the system is larger or smaller than the old one (changing cache sizes and the like).
If having very small downtime is an issue, and you have a very active database, you may want to consider setting up the new server to slave off the old server. Follow the MySQL replication documentation, setting up the new server as a slave. Then, when you are ready to make the change, you just start having your applications access the new server instead of the old -- perhaps by bringing the IP address down on one and up on the other, reconfiguring your application to the the new server address, etc...