It's easy to do with open-source software such as Solr (lucene.apache.org/solr) or Hounder (hounder.org, shameless plug because it is our product), which powers the wordpress.com site.
Edit: it looks like someone already did this: searchyc.com.
The day PG & Co adopt some piece of software that is made in Java... well, I can't even finish the sentence.
Either way, I think that PG is the king of guy who would rather work on his very special design (staying in Arc-land as long as possible) than adopting systems where you no longer have control.
Letting Paul work on the JavaScript makes sense, in this case. PG has no control over client-side code, so he prefers to not bother with it.
To integrate with Google, you talk HTTP, not Java. To adopt Lucene, you'll have to talk Java. There is quite some difference, isn't it?
There's no other search.
(edit: I'm not the one who voted you down)
If you remember some key words from the title, you can do a quick find in http://www.kirubakaran.com/phr0zen (snapshots of front page). It is not really search search but I find it useful all the time.