Hi,
I recently built an iPhone app with 86,000 rows and SQLite.
At first I didn't index my serach row and searches were taking about 1 second to execut on an iPod touch 2nd generation. Once I added my indexes searching was instant.
To be honest you might be able to get away with "like" queries on the field you are looking for? It might actually be good enough. I think you will find that once you add indexes to your data, the database is really going to grow in size and could make you app pretty big and putting a full blown search engine in there could be a real pain.
Here is some code to quickly do some tests for a SQLite database.
http://www.rvaidya.com/blog/iphone/2009/02/14/wrapper-classes-for-using-sqlite-on-iphonecocoa/
SQLiteResult *result = [SQLite query:@"SELECT * from test;"];
NSArray *row = [result.rows objectAtIndex:0];
NSString *firstValue = [row objectAtIndex:0];