Puedes hacerlo de varias formas, la fácil es la que comentas, un script en js que cada ciertos segundos compruebe si hay un nuevo mensaje con ajax, el único problema es que no es ni muy eficiente, ya que no sea instantáneo y dificulta la conversación, sin mencionar ademas el gran incremento de recursos que gastaras.

Lo ideal es que utilizar comet, o en su defecto pseudo comet, te dejo unos enalces para que vayas conociendo ajax:
- https://developer.mozilla.org/es/Ajax
- http://es.wikipedia.org/wiki/Comet

Tambien puedes utilizar: jabber, que creo que es lo que necesitas.
Un saludo