How does Cloud message services reach devices behind NAT / firewall? Getting push notifications with devices with a local IP works fine. I just wonder how is that it works.
Is it just uPnP? The device starts communication with the cloud messaging service and then IGD kicks in? So the mapping remains
Does the push notification client keeps a constant connection to the cloud server? I would like to think that is not the case.

I am interested specifically in how the push notification knows how to reach the device given it is behind a NAT or firewall. Is there a scenario where Google push notifications would not be able to reach a device?
As you might imagine, Google is pretty quiet with regard to its implementation details. So I'll just describe this in the general case and in a very basic form.

The way push is done is that the client (i.e. the phone) opens a TCP connection to the messaging server (e.g. Google). This connection is meant to remain open for as long as the phone is turned on. Fortunately a TCP connection uses absolutely no bandwidth when it's not transmitting anything, so it doesn't waste a lot of data, the radio transmitter can power down, etc.

The connection can remain open indefinitely, however behind a NAT, the NAT infrastructure keeps a table of open connections that it is handling, and drops connections that have been idle for some time, usually 10-15 minutes. Neither end gets notification of this. So this is handled by sending a TCP keep-alive packet which refreshes the entry in the carrier's NAT connection table. This only costs about 50 bytes or so, and only needs to be done every few minutes.