I use phpMyAdmin, your server may or may not have it installed - if not, you'll have to download it and install it manually, of course.
Anyways, if you DO have it do a complete dump of your database and save your .sql file. Once you switch servers, exract that file in phpMyAdmin. That's what I always do, and it works fine. I know there are ways you can do it with telnet too, but I'm not posotive how.
yeah phpmyadmin sucks for big DB's, I didn't have telnel or ssh on my old server so I had to back up each file individually. It worked fine but took about 2 hours total.