Update: Odiumjunkie sent in the following thoughtful analysis of TrackMeNot's robustness:
As it stands, the extension creates "random" search terms by combining words from a (very short) wordlist in a pseudorandom manner. The list can be seen in the extension's source code, and I also put it up here; http://tinyurl.com/f7n8u . It contains around fifteen hundred words - not nearly enough for the intended obfuscation to be effective, as it would be trivially easy for any party with access to the data to screen out search entries consisting only of those words.
Also, the search entries are limited to two-word terms, which makes the extension's effects even more redundant. The most revealing and sensitive search entries revealed by the AOL fiasco were things like "how to tell if ur gay and want to sexx0r ur best friend", entries that will be painfully visible, even among throngs of machine-generated two-word entries.
Even if the term selection was improved (say, by using real, human-entered search terms in a pseudorandom way, perhaps taking search terms from the AOL leaked data), the extension would still be of very limited usefulness, at least if you use Google for your searches. Google, I imagine through use of their pervasive analytics code, record searches made with no clicked results. This can be seen if you use the "Google Personalized Search" Feature and navigate to "Search History". Again, it would be trivial to ignore search terms made with no clicked results, making the extension's efforts redundant.
While it's a nice idea, this extension, in it's current form, really doesn't do anything to protect people's privacy. Far more effective would be to use the FoxyProxy extension for Firefox to reroute any contact with your search engine of choice through TOR. FoxyProxy allows you to specify persistant proxies for particular domains and supports wildcards. You could also use Extended Cookie Manager for FireFox to persistantly block cookies from the domain of your search engine. Not quite as neat as a single extension, but much, much more effective - by using TOR you replace your own IP address with an anonymous dynamic one, and by blocking cookies from your search engine you prevent the only other method of tracking your search patterns. No one can access your search data, because it will be almost impossible for the search engine to aggrigate it in the first place.