If your new host won't do it for you,
- Install WP at new host, as you would on any host - take a note of the settings in your wp-config.php and use these on new host and new database
- Copy your wp-content folder over to your new host. Depending on your user files and folders you might have to copy these over as well
- Install WP-DBManager 2.20 from here, http://lesterchan.net/portfolio/programming.php, on both old and new hosts
- back-up DB on old host, verify back-up
- restore back-up on new host
As a minimum, before you start playing about with it though, make sure everything is backed up and verified.