At the very least, you need SMT rework skills and tools, and you may need to route an additional address line. That sort of thing has been a lot more popular for upgrading wireless routers and other embedded linux devices, but I have not seen any reports of people trying to upgrade RAM in a Kindle yet. Be sure to publish your results.
EDIT: Because the upgrade to 256MB uses a power of 2 for the row and column address in the RAM chip(s), you probably do NOT need to add any additional address line in this case. You may also need to modify the u-boot bootloader (and perhaps other code) to initialize and use the extra RAM.