Android Cloud to Device Messaging Framework - Google Projects for Android
code.google.com
code.google.com
I thought Google Voice has been doing this for nearly a year and a half. Maybe not using the same C2DM framework you and I can use, but it certainly seems like they are using a push protocol like Google Talk & Gmail on Android use and are not polling all the time.
edit: it also looks like Facebook has been using C2DM since an update in December of last year:
http://www.androidcentral.com/facebook-andrd-finally-gets-ch...
In fact, we open sourced our C2DM Ruby Gem: https://github.com/sghael/speedy_c2dm