Searching is very important, as Google proved. Wikidot's search has sometimes been… well, imperfect. So I'm happy to tell you about the new version, which has been rolled out and is working nicely though not yet perfectly.
First, we have the local per-site search on each of your Wikidot projects. Second, we have a "global search" at http://www.wikidot.com/search:all that will search the whole of Wikidot, including your private projects, if you are logged in.
The new search engine, based on the open source Lucene engine, is faster and more complete than the old version. It still has some teething issues, such as not properly searching Cyrillic or Chinese. Let us know if you find any other problems with it.