Push Notifications in Android Platform
Google's official answer is the Android Cloud to Device Messaging Framework (deprecated) Google Cloud Messaging(deprecated) Firebase Cloud Messaging
It will work on Android >= 2.2 (on phones that have the Play Store).
(cross-posting from an answer I gave to a similar question - Does Android support near real time push notification? )
I recently started playing with MQTT http://mqtt.org for Android as a way of doing this sort of thing (i.e. push notification that is not SMS but data driven, almost immediate message delivery, not polling, etc.)
I have a blog post with background information on this in case it's helpful
http://dalelane.co.uk/blog/?p=938
(Note: MQTT is an IBM technology, and I should point out that I work for IBM.)