If you have shell access it's pretty easy:

mysqldump -uUSER-ID -p DATABASE-NAME > DUMP-FILE.sql

Where:

USER-ID is your mysql user-id
DATBASE-NAME is your mysql database
DUMP-FILE is the dump (backup) file you want to create

This will backup all the table structures as well as create insert statements for all your data. Then ftp DUMP-FILE to the new host.

On the new host you run the following:

mysql -uUSER-ID -p DATABASE-NAME < DUMP-FILE.sql

This will reload the data.

You can do the same thing with phpMyAdmin.