I have alot of data stored locally (10000+ data records) (not decided on how yet - this is part of the question)
How may I implement incremental search on this data (on a specific field)?
How should I set up the data locally?
XML? plist? sqlite?
Should I use Core Data for access?
You probably want to use Core Data and you certainly do if there is any kind of relationships between records. Without Core Data to manage relationships, the app's complexity can snowball.
It is a common misperception that because Core Data handles a lot of complexity automatically that there must be an inevitable tradeoff in performance such that, while Core Data may be easy to implement, it must therefore be the slowest solution. Turns out this is usually not the case because of the enormous amount of the tweaking Apple has done under the hood. It is rather hard to hand write a solution that can best Core Data for most use cases.
I recommend you start with the simplest Core Data solution and then get more complex only if you test the simple solution and find it to slow. I would start with just a brute force fetch and see if that is fast enough. The next step up would be to do fetches just on a single attrbute of the entity e.g. the name attribute of a Person entity, then fetch the entire entity only when needed. If that is still to slow, you will have to think about implementing some kind of tree structure in the entity graph (which is not to difficult.)
Premature optimization is the root of all evil. Don't try to make optimization decisions without data generated by testing. You will waste more time in the long run. Start simple and add complexity only when it is absolutely necessary.