I got an initial indication of interest e-mail from a recruiter at Google who had my resume on file from a while back. He asked me a couple standard non-technical questions, and then set up a phone interview.
My phone interview consisted of a couple sanity checks (e.g. "What does static mean in C++?") followed by one very tough technical question which lasted the entire interview.
That went well, so they brought me onsite, where I had 5 technical interviews, all 45 minutes each. They always seemed to run up to the limit/a couple minutes over, I think they should consider making the time longer. In the middle of the day I had lunch with an engineer for an hour who fielded whatever questions I had, but they don't provide feedback, so feel free to ask anything.
Each interview pretty much followed the same format -- they presented the question, asked me to go, I would say something like "Well the naive way to do it is ___, but let's look for the better way", but they would ask me to code the naive way anyway (usually). Then they would ask me how inefficient it is, how to improve it, and then ask me to code that. They wanted code (or pseudo code, if there were only a couple minutes left) in almost all situations -- they write it all down or just take a picture. At the end, each one turns it around to see if you have any questions for them.
My recruiter gave me status updates along the way, letting know what my status was, and it took about 3 weeks to hear back.
People: a couple interviewers seemed grumpy, like they didn't want to be there -- I didn't like that. But everybody, including the grumps, were really excited about their job, and really liked all their benefits/perks/freedom/situation in general.
Advice: the interviews are tough! Expect at least a couple months to review if you're rusty; study lots of books like CLRS; do a **lot** of practice problems (TopCoder is a very good resource); practice problems on the white board (I found this especially useful); bring in your own skinny white board markers -- the ones in the interview rooms are fat and hard to write with; be prepared to talk through your solution; bring several questions for all the interviewers (even just "how do you like your job?"); for things like quicksort/mergesort/merge/binary search, you should be able to write that in your sleep while you're drunk. Finally: google for "google interview questions". I was only asked one question that I had seen online, but preparing for the others helped me for the new ones I got.
