Assuming you are talking about the more expensive WiFi Kindle, it depends on what the signal strength is.
At my desk in London, it can take about 30 seconds, but down at my mum's in Dorset, I have to go to the end of the garden, and stand holding the Kindle as high as I can and it can take a few minutes.
If you live in a town, it will probably not be too long. If you live in the back of beyond, it might be a while!
Oh, and a quick tip - if you are getting the WiFi one, the battery lasts longer if you switch off the WiFi when you don't need it, ie when reading a book. Only switch it on when you want to download.