I had to do this for my mum's Kindle when my WIFI router died and I had it replaced.
It took weeks before I sorted out the kindle's connection to it and she was champing at the bit for more books.
Activated WIFI hotspot on my Desire HD search on the kindle for it and hey presto! Connected! Downloaded her books. It was dead easy.
And seeing as I work for Everything Everywhere (the merged company of Orange UK & T-Mobile UK), I get free data. So no charge.