C2DM required a Google ID, and now C2DM has been replaced by GCM which apparently does not require a Google ID.
Does this mean it is simply compatible with devices (such as the Kindle Fire) that does not have Google Play Appstore or the Google stack available to it?
Short answer is no.
The mechanism that actually receives the messages from GCM server relies on the Google Services Framework, the bundled services such as Google Play and GTalk are part of the framework.
If you don't have the framework installed you cannot receive messages from the GCM server. Basically it won't work if you don't have the Google Services Stack on your phone.
Refer to this link: http://developer.android.com/guide/google/gcm/gcm.html
It requires devices running Android 2.2 or higher that also have the Google Play Store application installed, or or an emulator running Android 2.2 with Google APIs. However, you are not limited to deploying your Android applications through Google Play Store.