1) Download all the Kindle books you've owned (either onto your device, or using the desktop reader - I think there is even one on Linux). You can mount a Kindle as an external drive, so you can easily move files to your hard drive even if you have too many to fit onto the Kindle.

2) Use Calibre to unlock the .mobi files, using the serial number (conveniently located under the "Device Settings" or "About this Device" menu - I forget which it's called, but it's a ~16 digit number and very easy to find.

3) Upload to S3

This works on Linux - I assume it works on OS X and Windows too.