Сценарий, который вы описываете, звучит идеально для C2DM. Если вы создадите свои собственные сокеты, вы потратите ресурсы батареи и процессора, делая то, что уже делает телефон - поддерживая открытый сокет для приема сообщений.
C2DM относительно прост в настройке, и по моему опыту довольно надежен.
Это лучший урок, который я видел на нем:
http://www.vogella.de/articles/AndroidCloudToDeviceMessaging/article.html
Но вы также должны прочитать официальные документы:
http://code.google.com/android/c2dm/
Ваш серверный код должен будет отправить HTTP-запрос на серверы C2DM, чтобы отправить сообщение на устройство. Чтобы указать, куда отправлять сообщение, вашему серверу необходимо указать Идентификатор регистрации (который представляет ваше приложение, работающее на одном конкретном устройстве), и поэтому, когда ваше приложение настраивается на устройстве Android, оно регистрируется в C2DM, а затем должно отправить его регистрационный идентификатор C2DM на вашем сервере, который будет сохранен, готов к использованию для отправки сообщений.