Where does the Foursquare notification come from?
When Google Cloud Messaging receives a message from Google, it sends a broadcast to the related app. The app can receive this broadcast even if no service was running, and it can respond by starting a service, or by creating a notification from within the broadcast receiver itself.

Part of the Android developers' documentation explains the process step-by-step. There's a lot of detail there that you only need to know to write an app that uses Google Cloud Messaging, but it might help satisfy your curiosity.