First, make sure Mint is up to date.
sudo apt-get update
sudo apt-get dist-upgrade -y
You will then need to update/download your Linux headers, per this article.
sudo apt-get install linux-headers-$(uname -r)
Once things are updated, keep the terminal open and cd into the appropriate directory. My ATI drivers were in the downloads folder. Once you've found and extracted the drivers, use bash to run them. It should look something like what I've typed below.
sudo bash ati-fglrx-versionnamehere.sh
You will enter the prompt and be asked which type of package you want to install, since the default packages are distribution-specific. You also have the option to build your own. Since you're using Linux Mint, it's likely that the package for Ubuntu 14/15 will work for you. However, you can also choose the generic installer and let the program do the work for you. I have found that it's not entirely critical to get this part right.
Note: At least in my experience, I received several errors -- especially without the appropriate headers. You can probably ignore these. The drivers will most likely still work.
Once the install is done, reboot and run the following command when you're back to your desktop:
sudo amdcccle
Hope it helps!