Android has voice recognition APIs built in, and if you are lucky, you can even get them to work offline. At any rate, using the SpeechRecognizer will get you a fairly turn-key solution for voice recognition.
However, I'm interested in implementing a Google Now style "hotword" (as in "OK, Google") that activates proper voice recognition. This hotword needs to be always-on, and for the sake of the battery and the user's wireless bill, it shouldn't use the network. In other words, how do I replicate Google Now's hotword functionality?
Have you tried Porcupine? The service demo is what you need for always-listening wake word detection.