There are a few threads floating around with info on this, but some of it is just a little bit off due to some changes in some things. They have the info needed in there, but buried along with other stuff. Going to do a step-by-step from a fresh install for those that are having issues. The main issue appears to be that the newest drivers DO NOT like kernel 4.4, so updating to kernel 4.8 could be all you need to do if you are having issues. After spending the day troubleshooting getting my RX480 running, I wanted to spend a little time making a concise to-do list for the novice. This may not be the ONLY way to get it working, but it does work and I repeated it to make sure. From installation start to everything working takes about an hour on my mediocre CPU and a standard hard-drive, your mileage may vary.
**Much of this comes from LuckyDuck99's thread, but AMD changed some things that messed up some of the instructions. So, props and much credit to him.
1) Install Linux Mint 18.1 from install DVD. Let it use 3rd party drivers for mp3s and stuff when it asks. After it finishes it will kick out the DVD. Take out the DVD, then hit 'Enter' to reboot.
2) After initial reboot click on the "Drivers" module in the welcome pop-up. Enable drivers that may be there that you want to use. For me that is AMD microcode. Reboot. (Some people may not need this step).
3) After next boot, update everything. Click on the "Update Center" icon beside the clock. Choose the middle option (do not choose the top one) for update center behavior. Update everything it wants to update. For me this was about 3 batches of stuff. At first it was a couple items, after that it gave a large amount of items, after those updated it did firmware and the 4.4 kernel. (May not need to update the 4.4 kernel since we are going to replace it, but I went with better safe than sorry.) Restart after updates to make sure everything is locked in.
4) On this boot, install the 4.8 kernel. Click the "Update Center" icon beside clock. At the top of the Update Center window, choose "View", then "Linux kernels". Click "continue" on the warning popup. Click on "4.8" on the left side, then click on the bottom 4.8 kernel in the list, and install. At time of writing this is 4.8.0-45. Reboot. (Edit: it also appears to work installing the 4.10 kernel that is now available, instead of 4.8. Both worked in my testing.)
5) This boot, download and install AMD drivers. In Firefox, go to http://support.amd.com/en-us/download/linux and download the Ubuntu driver listed for your card. At time of writing this is version 17.10-401251. (If you use a different browser that saves somewhere other than "Downloads", you will need to go to that directory when you install.)
6) Open the terminal (little black & white box by Menu). Need to go where the downloaded file is and extract the driver. Then, move into the new folder. So, type these at the prompt to do that. (The file name and directory will change with future driver releases, this is for 17.10 driver.)
tar -Jxvf amdgpu-pro-17.10-401251.tar.xz
7) Now, need to modify the install script slightly so it works on Mint instead of Ubuntu.
Scroll down until you see "ubuntu" listed below a section "function os_release". Where it says "ubuntu", delete that and make it "linuxmint". (Do not change anything else but "ubuntu" to "linuxmint"!!)
Hit "CTRL+o" to save, "Enter" to confirm, then "CTRL+x" to exit. Keep the terminal open.
8 ) Install the AMD driver.
Edit: that is "period slash amdgpu-pro-install -y" Sort of hard to see.
9) The user needs in the "video" group.
sudo usermod -a -G video $LOGNAME
Close the terminal, almost there.
10) Finally, delete the old driver. Open up the "Software Manager". (Menu, Administration, Software Manager). Search for "Radeon" in the search bar. Scroll down to "Xserver-xorg-video-radeon" towards the bottom. Double-click it, then uninstall.
11) ***Your AMD video card should now be good to go! Reboot!
12) If you want Steam, don't download from the steampowered website. Open the "Software Manager" again. Search "Steam". Double-click and install the Steam application there. Works like a charm.