Выше уже отметили: JSON или XML. От себя могу добавить, что таки JSON в плане эффективности немного лучше будет (гораздо меньше избыточной служебной информации), но XML можно валидировать с помощью написанных для отдельных запросов схем. Есть еще BSON, который еще эффективнее, чем JSON, ну и, например, ProtocolBuffers (http://code.google.com/p/protobuf/). Выбор должен зависеть от специфики работы связки клиент-сервер.
Ну и желательно написать этакий фреймфорк для для запросов/ответов, так работать будет проще. Например, для запроса обязательными полями могут быть номер, время запроса, версия протокола и некоторый payload, который и будет меняться в зависимости от типа запроса.