The Eclipse Guide (perhaps in a "Push" Section) needs to show how to resolve the GCM related dependency:

GoogleCloudMessaging is provided by the Android SDK. You need to import the Google Play Services project into Eclipse and reference the library from the AG project. The Services project is in $ANDROID_HOME/extra/google/google-play-services.