This is on Ubuntu/hardy. It's broadly the same for them all. It should work for the equivalent Mint version.
There are multitudes of guides on how to do this.
Download the driver to your hard drive. It will be named something like this:
ati-driver-installer-9-3-x86.x86_64.run
Look in the file /etc/modules. Make sure it does NOT contain the line 'fglrx'.
If it does, delete it and save the file.
Look in the file /etc/modprobe.d/blacklist-local. Make sure it does not contain the line 'blacklist fglrx'.
If it does, delete it and save the file.
Make sure you have the following installed. Not all are required but having this stuff never hurts. So open a terminal.
$ sudo apt-get update
$ sudo apt-get install build-essential ia32-libs cdbs fakeroot dh-make debhelper debconf libstdc++5 dkms linux-headers-$(uname -r)
Some of this guff is not needed/included in some Ubuntu versions.
While still in the terminal. Browse to the ati driver we picked up earlier.
$ cd/home/username/Downloads/ati
Now we will build the debian packages for Ubuntu.
$ ./ati-driver-installer-9-3-x86.x86_64.run --buildpkg Ubuntu/hardy
Replace the name on the end to build packages for your variety. (gutsy, hardy, intrepid)
This will create the following files:
xorg-driver-fglrx_8.593-0ubuntu1_amd64.deb
xorg-driver-fglrx-dev_8.593-0ubuntu1_amd64.deb
fglrx-kernel-source_8.593-0ubuntu1_amd64.deb
fglrx-amdcccle_8.593-0ubuntu1_amd64.deb
fglrx-modaliases_8.593-0ubuntu1_amd64.deb
libamdxvba1_8.593-0ubuntu1_amd64.deb
Now reboot into Grub. Press Escape when Grub appears.
From the menu select the recovery option.
After a short load you will be asked which mode you want.
Select root (drop to root console).
Now browse to the folder where the debian files are.
$ cd/home/username/Downloads/ati
$ dpkg -i *.deb
This should complete without errors. If you do get any errors at this point, you have problems!
$ aticonfig --initial -f
$ reboot
Good luck

If it doesn't boot then you will need to boot into safe mode graphics, get to your desktop and remove the packages via synaptic.
Or use apt if you want, of course. Then have a good think on why the install failed.
I've been using this method since 8.6 with no problems.
Not counting my first failed install using the 'installer', the only failure I had was when I tried the default installer with 9.1 to see if it worked.
Answer was no.
If you want the default installer to work I think the only option is to use Redhat/Fedora. It's the only one they really bother with apparently.