How do iPhone apps push notifications when the app isn't running? I've read some docs about notifications and background work, but there is something I do not understand.

Yesterday, I upgraded to iOS 4.2, rebooted my phone many times, and did not launch any apps. Then this morning I received a push notification from PandoraBox to inform me that an app I've placed in favorite had its price changed.

I wonder how this app, that is not launched, not in background, that cannot know in advance when the price of an app in MY favorites will change, can alert me with a notification this way?

It HAS to run some methods, some code… But I understood that that is not possible. What did I miss?
You must have launched PandoraBox before the reboot of your iPhone, right?

When you launch apps that send notifications, they keep the way to identify you and throw notifications to your phone. 

So the answer to your question is : "the code is running on some PandoraBox machine, not on your iPhone".