Yes, C2DM is ideally suited to this type of game. This is what I am using for my own game (http://www.chesspresso.net) which is a correspondence chess client for android.
Things to consider when using C2DM:
You don't send the info to the devices, you notify the devices that a move has been made. You don't use C2DM to transfer data, you use it to notify that something has changed.
Its available for 2.2+ Android, which is the majority of devices. But if you wanted to support older devices you'd have to consider an alternative. I am using polling for older devices.
You have to request for developer access, then once your app is ready you have to request production status. If you don't do this you'll hit the developer status quota very quickly once its released! They are very generous with production quota, but you have to explain what you're using it for and it also can take a few weeks to get accepted!
Your users will have to have a google account that is authorised, otherswise C2DM won't work. Most users will have an account associated with their device, but some don't so this means that you'll possibly want to validate for the presence of an account to notify the user.
Its reliable, but every now and again a device will have to wait for the message. Sometimes a few minutes. Usually its instant.
Hope that helps!
UPDATE:
C2DM has now been deprecated, and replaced by Google's GCM.
Also, I strongly suggest looking at other options as tying yourself down to a Google specific API means you won't be able to support external marketplaces. For alternatives, I am currently evaluating Amazon SNS and I will also be looking at Urban Airship. There are possibly other alternatives I have not considered evaluating yet.
UPDATE:
Evaluation update of non google based push notifications:
Amazon SNS is just not a project for this task and Urban Airship for the vast majority of apps is too expensive. Unfortunately all the other alternatives are all very expensive also, especially if your app (like mine) relies heavily on push.