It would work like so:
Whenever you install/delete an app on your phone, that information is sent to Apple and paired with your UDID. That way, Apple knows what apps you have installed and what version they are. When a new version comes out, a badge change is made on the App Store icon.
It's no more battery-intensive than any other push notifications are. Of course, it adds server-side load. Apple would have to make a new server in order to handle that load. Worth the cost? Probably not, considering Apple is not adding push notifications to the App Store as of yet.