Neste caso, eu particularmente, recomendo uso de um banco de dados NoSQL no lado Server pra atuar com uma performance minimamente aceitável (MongoDB).
Sobre sua pergunta, o WhatsApp por exemplo utiliza um conceito chamado SSL Socket (http://docs.oracle.com/javase/7/docs/api/javax/net/ssl/SSLSocket.html), não é um tema tão trivial, então você vai ter que estudar com paciência o funcionamento dele se quiser implementar.
nesse link:
http://android.stackexchange.com/questions/43970/how-is-whatsapp-able-to-receive-messages-when-not-in-usehttps://android.stackexchange.com/questions/43970/how-is-whatsapp-able-to-receive-messages-when-not-in-use
tem uma resposta bem legal (a primeira senão me engano) sobre a dinamica "app -> servidor" x "servidor -> app" para o funcionamento dos sockets...
lembrando que o lado server do whatsapp é feito em earlang, mas pra começar você pode estudar esse projeto feito em PHP disponível no GitHub:
https://github.com/venomous0x/WhatsAPI
Pelo menos pra começar é bom, pra captar os conceitos..