Ok, Im a little confused.

I CAN create a mySQL db using the control panel - that is by simply clicking the "Create new database" link.
BUT when I use phpMyAdmin (that is, by cliking on the top link phpMyAdmin and logging into phpMyAdmin) it says that "Create database: No priveledges".

Whats going on here?

And more importantly, where are the db files stored, I cant seem to locate the files?

It means that the user you are logged into phpMyAdmin with can't create databases. You should only need to create them from the hosting control panel.

There aren't physical MySQL files available to you. You can, however, back up the database from phpMyAdmin if you need to do that.