Yes you can. On my FireHd I down/side load my music and in the player there is a menu that allows me to create my playlists.
No cloud or internet needed, just the songs that are living on the kindle itself.
http://www.amazon.com/gp/help/custom...deId=201013280