I have created a Nautilus search backend for Tracker which enables you to do lightning fast indexed searches using Nautilus's new search interface.
If you are using a pre-release of Tracker, you will need to delete the hidden .Tracker directory in your home folder and then grab the latest source for tracker from Gnome-cvs (cvs -z3 co tracker).
Upon successful compilation and installation, you can then index stuff by running trackerd with an optional parameter specifying the full path of a directory to index (EG trackerd /home/jamie/Documents). If you omit the parameter, it will proceed to index your entire home directory. You can make sure that tracker only indexes a subset of your home directory by editing the tracker.cfg file in ~/.Tracker (which is created when you first run trackerd) and setting WatchDirectoryRoots=/home/jamie/Documents;
Once you have some indexed contents, you should now compile Nautilus (ver 2.13.4 or higher) which should auto detect that tracker is installed and automatically compile in tracker support. You are now ready to appreciate a powerful and super efficient c based indexer in all its glory... happy hunting!
To make sure trackerd always start when you login to Gnome, you will need to add it to Gnome-session (select sessions from preferences menu, select startup program tab and then add /usr/bin/trackerd). For non-gnome installations, see the desktop docs for how to auto start an application.
Coming soon, release 0.0.2 of Tracker which includes support for Inotify and some other optimisations.