You can use LaunchBar (or any other launcher/searcher-type app) to quickly search your Gmail by opening the configuration (go to 'Open Configuration,' or hit Command-Y). Scroll down the indexing rules and select Search Templates. Hit Add and title it what you'd like (I chose gmail). For the Details, enter:
http://mail.google.com/mail/?search=query&view=tl&start=0&init=1&fs=1&q=*
Now, you can open LaunchBar and type gmail query. When you hit Enter, your default browser will open with your requested search. This URL can be used in any other URL-based search tool as well, simply replace the * at the end of the query with that required for the specific software. For example, in Inquisitor, the url would be:
http://mail.google.com/mail/?search=query&view=tl&start=0&init=1&fs=1&q=%@
[robg adds: For Butler, just put everything through the last equal sign into the Prefix block for a new search engine; leave the Suffix block empty. Assign an abbreviation and/or a hotkey, and you're done.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20060306141308548