This is mainly due to how Push Notifications are designed in iOS. If the device does have a connection, it will be pushed to you through Apple's servers. Because of how push works (mainly with a device checking in now and then to say 'heres where I am'), you can get push notifications while the device is asleep. The notification comes through and pushes to the device.
With iOS 4, there is also the option for developers to use local push notifications. This mainly works by just setting a designated notification at some point in the future.
Update: According to this Apple Support Document, if the screen is on, push comes on at any time. If screen is off, checks every 15 minutes.