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!