일반적으로 푸시 메세지를 사용합니다. GCM(Google Cloud Message)라고 하죠.
서버가 app으로 메세지를 보내고, 앱은 그 메세지를 받아서 지정된 동작을 수행합니다. 리시버에 의해 동작하기 때문에, 앱이 실행되어 있지 않아도 상관없습니다.
카톡 같은 경우에는 별도의 서비스를 돌리기도 하는데, 아마 푸시 메세지가 누락되는 걸 보정하기 위한 polling이나 sync 기능이 아닐까 싶습니다. (이 부분은 그냥 개인적인 추측입니다)
푸시메세지가 100% 전달되는 것이 아니라는 점은 중요합니다!!
아래 링크에 보면 GCM으로 클라이언트/서버 만드는 내용이 나옵니다. 참고하세요. (지정된 링크는 클라이언트고, 목록에 서버내용이 나오네요.)
http://cholol.tistory.com/169