JSON или XML работали лучше всего для меня в прошлом. Существует несколько форматов, которые iPhone SDK обрабатывает изначально (plist), но я бы избегал их, поскольку вы можете открыть свой сервис для других клиентов в более позднее время.
iPhone SDK включает в себя парсер SAX (NSXMLParser), но вы можете свободно импортировать другие библиотеки, такие как libXML, если вам больше нравится DOM. SAX вписывается немного лучше в места с малым объемом памяти.
Для JSON вам понадобится сторонняя библиотека ... Я думаю, что SimpleJSON - один.