How do push notifications work? What is the basic concept behind them?
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) 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.