Alright, as far as I can tell, it is impossible to root the fire tv stick as of yet. Hopefully someone comes up with a way. I'll just drop some instructions from the beginning and add a few resources for people starting fresh. I uploaded the settings.apk I used, so be sure to grab that from this post. Before I get too far into this, everything I have done is with a stock Fire TV stick and Nyko gamepad controller straight out of the box, and anything done to the fire stick is listed below.
On the fire tv stick, make sure under settings that the adb debugging and allowing outside apps are enabled. As for getting the settings.apk to the stick itself, just follow the instructions found here: sideloadfiretv.com/sideload-apps-amazon-fire-tv-windows/
(Being a new user, I cannot link that, so I apologize for the inconvenience)
Once that is loaded, go to Settings>Applications>Manage Installed Applications. Find the settings app, launch it, and go to the bluetooth menu option. Click it, and up at the top right hand corner, you will see an option that will allow you to search for bluetooth devices. Make sure that the nyko remote is charged, turned on, and set in the gamepad function before clicking that option. Once you have the gamepad set up, click the option to search for bluetooth devices, it may take a minute. Once it picks it up, enable it in the menu, and you should be good to go.
I did not change any functions on the controller itself. This is the stock Nyko gamepad controller straight out of the box. You will be able to switch it back and forth between the controller and mouse functions, and both work. The only thing I have found is that when entering user names and passwords on apps, keep the stick remote next to you, as it is generally easier to use that to enter the names/passwords/etc. I have successfully navigated and watched stuff from the DirecTv, Funimation (though this app is still a little funky to navigate, it works), and Xfinity sideloaded apps.
As far as games, my kids are playing Sonic 2 with the controller currently, and there are no issues with it. It works great. Just remember to turn it on and off when using it and not using it, since it has a chargeable battery.
Sorry Y314K, I am sure that this is far more more information that you originally wanted/needed, but I figured I better start from the beginning, so newbies reading this will have all the tools they need to make it work.
Hope this helps!