Where does the Foursquare notification come from? Yesterday, I got a Foursquare friend request in the notifications panel.

The only running services at that time were, I believe, the same that are running now. Definitely there was no Foursquare service running. I hadn't used Foursquare in weeks. From Settings:


Settings
Google Services (GoogleLocationService)
WhatsApp
My Calendar
Google Services (Cloud to Device Messa…, Google Messaging Ser…)
Maps
Android keyboard


I was logged into Google Latitude.

By what mechanism did the friend request reach the notifications panel?
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.