Am I correct in thinking that I can do this with the help of PHP?
Yes, PHP can be used as a database scripting language. It is quite easy to learn and pretty powerful as far as a web language goes. You need a web hosting company that supports PHP. If they don't, convince them that they should. 🙂
I have read the basic tutorial on linking the database with PHP, do I just upload the access database to the website?
First off, I assume that you are not hosting your own website. You need to find out from your web hosting company if they have provisions for databases and if so, what databases they will let you use. If it is an NT Server then ODBC will be your database connection type. If it is Unix or Linux then there are quite a few different databases they could be using. If they are not using databases then your only option will be to make your own using text files for data storage. (Not really that difficult unlesss it is a huge database)