Как создать на сайте обмен личными сообщениями? Желательно с нуля.

Да как-как! Тупо. Те же базы данных. Табличка с ЛС. В ней поля необходимые - там, ID, получатель-отправитель, дата-время отправки, текст сообщения. В простейшем случае так. Ну и все, дальше уже фурычишь с серверным языком, чтобы все выдавалось куда надо и как надо, чтобы невозможно было взять не свое сообщение, и прочие элементы безопасности...