Самое простое решение, которое я нашел, это RegexKitLite:
http://regexkit.sourceforge.net/
(обратите внимание, что версия "Lite" - та, которую вы используете для iPhone)
Всего два файла для добавления в проект и флаг -licucore для компоновщика. Он использует встроенные способности регулярных выражений.
Он имеет расширения NSString, в том числе для замены, а также может извлекать несколько совпадений по номеру.