I've checked the new Kitkat libraries to make sure that I'm not missing something. I want my application to always listen to a keyword before performing an action, just like how Google Now always listens for the keywords "Ok google" on the homescreen.
How did Google accomplish this?
What you need is called keyword spotting. Apart from online speech API Android has offline recognizer which is a bit more sophisticated. It is not mentioned in official documentation, but you can see the sources here, for example. I'm not sure you will find keyword spotting there, but at least you will have access to low-level recognizer interfaces.
UPD: Keyword spotting and voice activity detection are now implemented in pocketsphinx and pocketsphinx-android. See the official demo to see them both in action.
Services can be kept running in the background! They probably invoked it by setting a broadcast receiver to receive the boot completed broadcast and invoking a service which is set to listen for the phrase.