Rootear o seu Kindle Fire é simples. A melhor forma que eu encontrei foi usando o BuritoRoot3.
Eu usei o Root para poder adicionar o Market e o Swype, mas você pode até, usando o FireFireFire que vem junto com o BurritoRoot3, substituir a ROM por uma ROM customizada do Android 4.0 para Kindle Fire.
Para isso, é necessário que seu Kindle Fire já esteja acessível pelo console, como já descrevi aqui.
O passo a passo oficial é esse.
Bom uso!