First, you should install phpmyadmin http://www.phpwizard.net/projects/phpMyAdmin/ since I gather that your web hosting company isn't very helpful in providing links or a database management console.
If you can get phpmyadmin working correctly, then you're in business and can read some tutorials 🙂
There are some exellent tutorials about php + mysql at http://www.devshed.com. They cover most stuff that you'll need to know.
http://www.phpbuilder.com has other tutorials you will be interested in.
As far as web hosts, if you are looking for a cheap one that will be ok for developing php & mysql pages for a very low traffic web site, check out http://www.phpwebhosting.com.
If you need faster response times and telephone support, I would suggest http://www.communitech.net