I’ve never transferred a website before let alone a database. I believe I backed up the database to an .sql file and I haven’t deactivated the old host yet in case I need to do it again.
My main question is now that I’m on a host with cPanel should I use the automatic “WP Install” and then upload the database somehow or should I just follow Moving WordPress and just upload all of my folders and files from the backup?
You can try the manual transfer, first copy all your tables on your new database. Then you need to update the wp-config.php file in order for it to be able to connect. In case you have the rewriting enabled, you may also need to update the htaccess file (if the rewritebase is different, it’s not that likely but it may happen).
Also check the chmod of your folders/files, there is an article about that.
After fumbling a bit with the database I came across http://codex.wordpress.org/Importing_Content
Switched the nameserver back, got into the old wordpress, did an export from in there so it would be in the xml format it wanted instead of sql. Switched the nameserver again to the new host, did a fresh WP install and imported the xml file from within wordpress.
No database, phpmyadmin or mysql required!