Android's voice search also does things in the cloud. It's not bad, actually. I can say, "Email Alex. Subject Hello. Body Hi Alex, how are you [question mark]" and my Xoom will open the gmail app and fill out all the fields in about 3 or 4 seconds.
I imagine Apple will be approximately the same.
A lot of the rumors seem to indicate that it's an iPhone 4S feature because of processing power requirements. It sounds as though there is a lot of processing happening on the device. It goes to the "cloud" for looking things up that aren't on the device itself. Wikipedia, Wolfram Alpha, Weather, etc.
I'd imagine they down-sample the audio like crazy. They certainly don't need CD quality sound for it.
the standard is 8kHz-16kHz, 8-bit PCM. higher frequencies are of limited utility in recognizing human speech.
I find Google's version of this pretty zippy and useful, so I'd expect it will be at least as good as that. It's usually a ~5 second turnaround, I'd estimate; I typically use it if I'm walking to catch a bus or suchlike and don't want to slow down or have an accident by typing at the same time.
I think it depends on the carrier as well. Sometimes on my Droid 1 on Verizon it can take a good 10 seconds to get a get a response or 10 seconds to make the initial connection to the server to allow me to start talking.
Is it done in the cloud? Why would it require an iPhone 4S then?