일단 developer.android.com에서의 Push Server구현을 잘 읽어보시면 됩니다.
Push서버는 그냥 GCM과 통신해서 단방향 Push가 있고
XMPP 서버를 이용한 양방향 Android <-> 서버 Push가 있습니다.
XMPP는 2009년쯤에 Google talk에 사용되는 무료 채팅 프로토롤(?)입니다.
2009년쯤 제가 P2P 스마트폰 Android, iPod Touch g2에서 p2p자료 검색엔진을 구현할때 사용했는데
이제는 양방향 push서버를 구현하는데 사용되네요.
XMPP는 채팅서버로 보시고 MSN(없어졌지만) 을 분석해보셨다면 이해가 될겁니다.
아래의 글을 참고하세요. 쉽게 구현할수 있을겁니다.
GCM Cloud Connection Server (XMPP)