I had Play Store working before and I rooted my Kindle Fire HD 8.9".
What happened was my 4 year old niece tried using Kindle but she didn't know the pin so she just pressed and held some buttons. I think it was power button. After that Kindle took very long to start, asked me to login into Amazon again and all apps were gone. I think she factory reset it. The root stayed.
Does this method make it persistent or will I have to redo everything if it were to happen again? Maybe there could be something automated to get me back to where I am now with backing up and restoring or something.
This method does make it persistent since everything is placed in the /system/app folder. We are working on a simple How to: Backup and Restore the Kindle Noob (Simple) Version. Since it is involved, we need another 48 hours but look for it soon.