How has Google implemented their push notification feature? Does it work through polling done by a service running in the background or in a different way?
From what I've heard during an Android developers conference in Israel:
There is simply a TCP socket waiting in accept mode on a cloud Google server. The TCP connection had been initiated by the Google Play application. That's why Google Play must be installed on the device for making Google Cloud Messaging (GCM) (formerly Android Cloud to Device Messaging Service - C2DM) work.
When this TCP client socket receives some message, the message contains information such as the package name of the application it should be addressed to, and of course - the data itself. This data is parsed and packed into an intent that is broadcast and eventually received by the application.
The TCP socket stays open even when the device's radio state turns into "idle" mode. Applications don't have to be running to receive the intents.
More information at http://developer.android.com/google/gcm/gcm.html