iPhone 4s: I keep receiving notifications over 3G for apps that I've disabled cell data for I try and keep an eye on my cell data so I don't use too much. From what I've noticed from my own usage the apps that eat up the most data are the ones that stream music and videos like Pandora and Youtube, so I turned off cell data for these apps. Just yesterday I got a notification from Pandora saying "New music has been added to so-and-so station". I wasn't on wifi and after double checking the cell settings data was still disabled for it. 

Whats going on?
When you disable access for cellular data for specific apps like Pandora and YouTube, It only disables the access cellular data when you have the application open.

The push notifications you receive on your iPhone are sent through the Apple Push Notification Service (APNS). This is done so that the application does not need to run at the background to fetch new notifications all the time, Only the Apple's push notification service runs all the time checking for updates from all the applications.

All the more the push notifications uses a very minimal amount of data which won't be shown in the usage.