How does Cloud message services reach devices behind NAT / firewall?
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.