Skimmed through this thread a bit so apologies if I repeat anyone too much.
As stated Gmail and some other features (calendar, voice, etc.) are indeed push-based. Some older versions of the software may be using pulling though (e.g., Google Voice used interval pulling until the most recent update), so that's something to look at if you are having issues. I see a ~5 second delay between sending an email from one account and seeing it in a separate account on my phone.
Apple's service works in the way you would pretty much expect, i.e., in an extremely limited and controlled way. An application registers itself against a developer's database. That developer's servers or the application itself can determine when a push should happen. If this happens on the servers (e.g., breaking news), those servers communicate push tokens, application IDs, message, badge, sound, action, etc. to Apple's servers. Apple's servers then communicate to the iPhone (or attempt to). The total payload is limited to 256-bytes, so you can't send anything significant in this manner. Since it all goes through Apple's servers you can't (well, shouldn't) send anything confidential either. Each iPhone keeps a socket opened with the push notification servers all the time. Since all the notifications are funneled through this single service, it can be more battery efficient.
One major problem is that you can't cause the app to do something in the background. For instance, a third-party mail app cannot see the push if it is not opened, so you can't have it download an email in the background. Instead, the user gets an amazingly obtrusive notification on top of the current activity and has the option to open the app. In this regard, it is worse than the pull methods incorporated by many Android applications. You couldn't ever use Apple's push notification servers to keep an offline sync of RSS feeds, for instance. Apple's push servers also receive the "don't send me more push notifications from X app" requests and the developer's servers have to constantly grab that data and update their databases or risk being blocked from the service.
The certificates used on the developer's service also have to match or Apple's servers instantly drop the connection with no error message. They can also drop the connection for no apparent reason, and they also have to way to guarantee or verify delivery.
Hopefully that clarifies some and answers a few of the questions. If you can't tell, I've had to do a lot of work with push notifications lately, and it wasn't fun.