It's not live. It's a routine check much like mail would do. I think it checks once a day though, because I often open up the App Store to find that the badge that said "1" was incorrect, and there are actually 3 or 4 updates. It's been this way since the 3G though I think. Whatever they're doing it's been the same since before push notifications existed.
Originally Posted by Justin
Not really, Push Notifications refers to much more than just email, and in the case of the iPhone, email is probably the least common use of Push notifications, because most users don't know how to setup their gmail addresses for push.