Be very good at off-the-cuff 80% solutions to topcoder problems on a whiteboard, which I am. So much so, that when they told me to use whatever sort algorithm I wanted to, I used bubblesort on purpose, to prove a point, and got away with it. Later on, I reduced another interviewer's search problem to a polynomial equation that had integer roots when a solution existed (at which point he asked me what I'd do on an architecture that didn't have a square root or a divide function and I replied "and what modern architecture would that be?"). Which is to say their interview process is a computer science puzzle game IMO. The skills displayed here have at best a loose correlation with one's engineering skills, and that non-correlation shows up like crazy in their codebases (but Steve Yegge already covered that far better than I can).
So if you are a demo coder at heart, and you've been paying attention to whatever technologies are the flavor of the month at google interviews by reading blog entries like this (apparently javascript these days), you'll do just fine.
In my case, it only took one round for me to get the offer which I (unfortunately) accepted (but the tale of my 4 godawful months at google thanks to naively letting myself get blind-allocated into the wrong team is a different story).
Google is a great company, really it is. I know lots of relatively happy people there, but focusing on the interview process is a mistake. The real challenge is to get yourself hired onto a good team by resisting all the pressure they exert to persuade you to jump into the blind pool, which is a recipe for russian roulette. The solution, which in retrospect I smack myself for not doing the due diligence to find out, is to insist on getting allocated to and speaking with your future team as a condition of accepting an offer. Do not compromise on this point.