Update July 15, 2010: I should have posted this a long time ago, but the BEST way to move your Joomla site to a new server is to use Akeeba Backup.
The most popular article on this site covers How to move your Joomla! site to a new server, but it does not cover all of the details for moving your Joomla! 1.5 site to a new server. This how-to discusses the process of moving your Joomla! 1.5 site to a new server. The information contained in this how-to also happens to be an excerpt from my upcoming book, Beginning Joomla!. (Due out in early April)