Google Cloud Messaging GCM. It's free. It's unlimited. It's maintained by Google. And it's already installed on user's phones.
That being said, the ideal way now is to use Google Play Services and have people login with their Google+ accounts. Watch the last Google I/O 2013 session on Google Play Services. The demo went wrong during the general keynote, but it works fine otherwise.
Google Play Services takes care of all the networking issues for you (and also falls back to local wifi if users are on the same network). The price you have to pay is that you must force your users to use Google+ if they want that multiplayer functionality.