Download the full install (I believe the link is at the bottom of the page that has your license key). Unzip it on your PC, and look at the README file. It had enough info for me to get it installed the other day.
You can create the database in cpanel under "MySQL databases". Create a database called whmcs. It will actually be named "<yourdomain>_whmcs". Then create a user (if you call it admin, it will really be called "<yourdomain>_admin"). Then you'll need to assign all privledges to that database to the user you just created.
As for where to upload, that will mainly depend on where whmcs will fit into your site. If you want it in a subdirectory called "clients", or "support", then rename the whmcs folder in the download to whatever you want it called, and upload the folder and contents to public_html. If you want whmcs to "be" your site, then you can upload just the contents of the whmcs folder to your public_html directory (this is what I'm doing). There is also an ioncube folder there as well. I don't know if you'll need it or not, but if you do, upload it to your public_html directory as well. There is also a status folder with the script that shows your server status. You can put it in public_html as well.
Then, chmod the files that are specified in the readme, and run the installer (go to the install.php page in a browser). Answer the questions (don't forget to prepend your domain name to the user and database), and it'll take care of it from there.
Give it a try, and let me know if you have problems. I'm sure we can get you through it.
John