These batteries start to die from the date of manufacture and the number of charge cycles doesn't have much impact; they will get about 3-4 years. Amazon currently says they will replace your battery (although I would guess it is actually a swap for a different Kindle) for about $70.
This site has a replacement battery for $30 including a tool to get the back off. Given the vast user base of Kindle, I would assume that there will be batteries around for a while.