I recently modified the original greasemonkey script that added persistent searches to Gmail. Instead of storing the saved searches only in a cookie, the data is also saved in a Gmail contact. This allows the saved searches to go with you even if you change computers. Also, it prevents users that use the same computer to see your saved searches when they log into their account (or if you happened to have 2 gmail accounts).

More info here:
lukebaker.org/archives/2005/05 ...