Here is a Link to the GCM Client Application from Google.
http://developer.android.com/guide/google/gcm/demo.html
After it, you will have an (NAtive) App, which can receive message from Google Cloud Messaging Service (GCM)
You are able to receive these notifications after the first run.
You will also need a server to initiate the Calls to your app. If the message receive, your callback routine will be called and you can do what ever you want, e.g. Displaying the message or leading to another (maybe an MobiOne App)
I will appeare like in Wether apps…you get a notify, and when you click, the weather app will be startet to fetch the actual new informations.
I did it for an Informationservice to notify the user, if new Measurements for him are stored in the server database.
To send the Notify to the Mobile Device, there are services who abstract this layer for Android AND Iphone, so you have not to program it for each plattform.
Hope That helps.