Olá, 

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-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..

espero ter ajudado.

vlw