Learning to create and use threads is fairly simple,learning to make your code thread-safe is much more difficult and can require (depending on what the thread does) a fairly good understanding of concurrent programming concepts such as mutually exclusive access to shared resources, deadlock, livelock etc. Whole university courses are dedicated to these concepts alone. If you are unfamiliar with threads, I would expect that you are probably unfamiliar with these concepts as well. I don't want to discourage anyone from learning to use threads, multi-threaded programs are the only way to go for solving certain problems, and threads can be very powerful tools if used correctly, but I want to emphasize that it's not usually as easy as simply creating a thread and turning it loose.
I don't really know of any good web tutorials on threads, I'm sure you could search for them as easily as I can, but if you're interested, I remember a fairly good introductory tutorial in one of the C++ Builder books I have, I'd just have to find which one it is.
One additional point: You mentioned that by using the ProcessMessages() solution, the user is able to continue working while your search is still in progress. That really isn't completely true. One main difference between threads and the ProcessMessages() approach, is that the ProcessMessages() approach is a sequential rather than a concurrent or parallel approach, meaning that your program is really only doing one thing at a time. Any time your program responds to another message, your search is being suspended while it responds to that message and executes whatever code is associated with it. If that code happens to take a long time to complete, your search is interrupted for a long time. Once that code is complete, the search is resumed until another message comes along. In a multi-threaded approach, multiple threads of code actually are running concurrently (or at least sharing cpu time and system resources), so each thread can operate completely independently of any other thread.
I'm sure that's more than you were asking, but hope that some of the info helps.