Leo en la consola de desarrollador que el servicio de notificaciones push Cloud To Device ha salido de beta y pasa a llamarse Google Cloud Messaging. Tiene muy buena pinta porque parece mucho más fácil de usar, especialmente desde la parte de servidor. Y admite mensajes de hasta 4 KB.
Aquí el API:
http://developer.android.com/guide/google/gcm/gs.html
La parte de servidor la han simplificado mucho al ofrecer una biblioteca Java que lo hace todo.
Igual que su antecesor, solo es válido para dispositivos Android 2.2 o superiores que tengan Google Play instalado (aunque la aplicación no necesita haber sido descargada de Google Play)
Si alguien se anima a probarlo que comente impresiones
P.D: De momento lo que no me gusta es la retaíla de permisos necesaria, para versiones anteriores a Android 4 necesita WAVE_LOCK, GET_ACCOUNTS, etc...