У вас уже есть связь, установленная из вашего приложения Android на сервер приложений (например, HTTP) - в противном случае C2DM не принесет вам пользы. Используйте все, что вы уже используете, для обмена данными из приложения Android на сервер приложений, чтобы отправить регистрационный идентификатор на сервер приложений.