It looks as if Amazon did not patch the standard method to root ICS devices discovered by SparkyM over at XDA, and the Kindle Fire HD can be rooted in mere minutes. In fact, the most difficult part is getting the device driver if you're running Windows. Also note that rooting does not mean the same thing as a custom ROM, and that this has nothing to do with the bootloader which is unsurprisingly pretty securely locked up.
You'll need to have the Android SDK installed, and follow the instructions in the forums. You'll also need to know that you could really break things while rooting or running apps as root. Informed decisions are the best decisions. Good luck!