Google has registered a voice-actived search patent. Patent number 7027987 refers to "a voice interface for search engines. Through the use of a language model, phonetic dictionary and acoustic models, a server generates an n-best hypothesis list or word graph." It seems that Google has had the project in the works for some time, and that a demo of Google Voice Search has been up on Google Labs for over a year.

Google Voice Search, still up on Google Labs, allows people to call into Google by phone. Though the demo on the web page was inactive when's sister site Cnet tried to test it, the instructions show that this is how the system is meant to work:

Searchers call a Google supplied number, where a prompt asks them to "Say Your Search Words." After a minute, the results are returned and, in the demo, the searcher clicks a link that leads to them. In a real-world application, the results would presumably be sent to a mobile phone screen or in-car system.
In the future, it may be possible to do Google searches using voice via a mobile phone.