I updated this guide after JB came out, I recommend using it instead.
So I bought one of the Refurbished Kindle Fires off of Amazon recently and decided that I wanted Android 4.0 instead of the stock stuff. Looking around I realized that there wasn't one guide to just go through the whole process so I threw this together of everything I did to help anyone else who had some trouble:
1. Get the Kindle Fire ready
Go to Settings->Device and update to latest release (6.3.1 at time of writing) and Allow Installation of Applications from Unknown Sources. Picture
1a. Install drivers
This step didn't work for me, but if it does work you can skip steps 2 and 3. Download Kindle Fire Utility (0.9.6 at time of writing). Unzip and run as administrator (right click on file) "install_drivers.bat". Let that run and run "run.bat" in Kindle Fire Utility, assuming it works as intended you should see ADB Status: Online and Boot Status: 4000. If so skip to step 4, otherwise continue to step 2.
2. Install the Android SDK
Now install the Android SDK, which will let your computer communicate with your KFs internals. The download links can be found here. Install Extras (at least the Google USB Driver), Android 4.0, 4.0.3, and Tools. (Be sure to choose "Approve All")
3. Enable ADB access
First connect your Kindle Fire to your computer and let the drivers install (WARNING: You must use USB 2.0, the Kindle Fire doesn't like rooting through USB 3.0). Then navigate to the [your user name]/.android folder. Edit the adb_usb.ini file, adding the following line of code at the end:
0×1949
Close and save that file.
Find the folder where the SDK was installed and open the google-usb_driver folder (C:\Program Files (x86)\Android\android-sdk\extras\google\usb_driver). In that folder, find the file android_winusb.inf and add the following code to both the [Google.NTx86] and [Google.NTamd64] sections:
;
;Kindle Fire %SingleAdbInterface% = USB_Install, USB\VID_1949&PID_0006 %CompositeAdbInterface% = USB_Install, USB\VID_1949&PID_0006&MI_01
Now you can close and save this file as well. In your start menu choose "Devices and Printers". Double Click on Kindle and then "Update Driver..." Select "Browse my computer for driver software" and navigate to the C:\Program Files (x86)\Android\android-sdk\extras\google\usb_driver folder. When you're prompted choose "Install this driver software anyway."
(Note: I had a bit of trouble with getting my computer to recognize the ADB status of my Kindle. What I did was uninstall the drivers right after my Kindle had been plugged in and then installed the android_winsub.inf file. This is what my Kindle Properties looks liked when plugged in)
4. Time to Root!
Run "run.bat" in Kindle Fire Utility, assuming it works as intended you should see ADB Status: Online and Boot Status: 4000. If so then run "2 Install Permanent Root with Superuser" Let that run and you should have root!
Note from winteriscoming2
Windows 7 64bit has some problems with running .bat files. Users should try to opening the command prompt as administrator and then running run.bat from there.
4a. Installing GApps and Go Launcher EX
This step is ONLY if you don't want a custom ROM. If you want a mostly stock Kindle Fire experience but the ability to use Google Play apps then stop after this step. Otherwise continue onto 5. Once your root is succsessful go back into KFU and run "6 Extras <Requires Root>" then run "1 Install Google Apps / Go Launcher EX". Once that runs you'll have Google Apps and Go Launcher. If you don't want Go Launcher just uninstall it. Reboot your Kindle Fire and you'll have Google Apps and root!
4b. Temporarily Unroot
You should also install Voodoo OTA Rootkeeper on your rooted Fire so that you can unroot when you want to watch Instant Prime Videos and use the Lending Library.
5. Install Recovery
Now that you have root leave it plugged in and go back to the Kindle Fire Utility. Now you should still have the same ADB Status and Boot Status. If so then just run "3 Install Latest TWRP Recovery" and let that run, you should now have Recovery!
6. Install Rom/kernel
Download gedeROM (1.7 at time of writing). Transfer the .zip file onto the Kindle Fire, just put it straight into the drive folder (i.e. if your computer recognizes your Kindle as F: just place it in the F: not F:\TWRP or anything, this is referred to as the sdcard of the Kindle Fire).
Now reboot (Initial Boot Screen and Boot Menu) into Recovery. Choose "Wipe" and then choose "Factory Reset". Finally go back to the main TWRP screen and choose "Install". Navigate to wherever you downloaded the .zip file to (screenshot, scroll through the list, choosing ".." lets you go back to the previous folder) and press the .zip file. You should get a screen like this. Swipe to flash the ROM and let it run. Then just navigate back to the first screen and choose Reboot->System. Your Kindle Fire is now running ICS!
NOTE If you are missing the market or similar core apps, you probably need Gapps. ICS GApps or JB GApps
Revert back to Stock
If for some reason you need to send your Fire back in for repairs, giving it to someone, selling it, etc... that requires your Fire to be unrooted and on stock it's pretty easy. Download the latest software update from Amazon. Rename the "update-kindle-6.3.1_D01E_4107720.bin" file you downloaded as "update.zip" (make sure you changed the extension and that it's not update.zip.bin) It's exactly the same as step 6 above Install Rom/kernel but instead of installing gedeROM you want to use the update.zip file you downloaded/renamed (boot into TWRP, wipe cache/delvik/factory reset, flash update.zip, reboot).
My next goal is once FIREFIREFIRE Extended updates to 1.4A and MoDaCo updates to 6.3.1 to set up a dual boot for my KF so I can have both ICS and stock. Then all I'll need is Voodoo OTA Rootkeeper to temporarily unroot my KF so I can use the Lending Library. Once I manage that I'll write a new guide.
Let me know if anyone has some advice to make this friendlier/better!
Edit: Also for the CPU Governors (Settings->System->Performance), I was a bit confused by what they all did, so here's a general Android CPU Governers. Be sure to set your Maximum CPU Frequency to 1200 MHz! (Note: to save your OC and chosen Governor you must check "Set on Boot"
Edit 2: Thanks to SubaDivingElephant for informing me that you CAN watch Prime Instant Videos through the web browser on ICS. I just added a bookmark with a link to Prime Instant Videos. Only thing left now would be the lending library.
Shameless Plug: Same style guide for root/kernel/recovery/rom on the Galaxy Nexus