On the Android Hive there's a recent tutorial posted showing you how to use Google Cloud Messaging and PHP+MySQL to do push notifications on an Android phone.

As per google’s documentation “Google Cloud Messaging for Android (GCM) is a service that helps developers send data from servers to their Android applications on Android devices”. Using this service you can send data to your application whenever new data is available instead of making requests to server in timely fashion. Integrating GCM in your android application enhances user experience and saves lot of battery power.

You can either follow along with the tutorial via the screencast (and download the code) or you can read through the text version, complete with code snippets, SQL and screenshots to help you along the way. The code for the Android side is included as well.