The in-device search not allows you to search through various categories of data. Categories include: Music, Contacts, Calendar, Messages, Email messages, Bookmarks, Images, Videos, Landmarks, Applications and Notes. You can either search all categories simultaneously or, by pressing right of the direction pad when the appropriate category is selected, search in only on category.
The search is continuous meaning that results will updates themselves as you enter your search term.
This is an extremely powerful application and is a very welcome inclusion to Nokia's S60 software suite.
Nokia Search provides a more powerful search functionality than that which is built into in various standard applications. In the Contacts application, for example, the search is by first name / last name, but Nokia Search searches across more fields (though in my tests I found it seems to only index one phone number per contact - the most recently entered).
Also worth noting is that Nokia Search only indexes full words, thus to search for 0800123456 you would need enter '080012', '123456' would not work (this is really only an issue with number searches).
Although an Active Standby plug-in is provided on handsets that ship with this version of search (N81, N95 8GB) it does not appear to be available in the downloadable version which is a shame. However you can get much of the same speed by using one of the standby application shortcut slots for Nokia Search (configurable via Tools-> Settings-> Personalisation -> Standby mode).
The older versions of Nokia Search remain available for other handsets. Further updates may become available for other handsets in due course.