The Samsung HS3000 paired up easily with the Fire HD. One of the nice features is that you can control all the major music functions like Pause, Play, Volume etc. from the Samsung controller. Very reasonably priced on Amazon and sounds pretty good too.
http://www.amazon.com/gp/product/B00...ls_o01_s00_i00