I applied through a recruiter. The process took 4 weeks. I interviewed at Google (Mountain View, CA) in May 2011
Interview
I had one phone interview and then an on-site interview for this position. The phone interview was a 45 minute technical interview including programming over Google Docs, and the onsite consisted for five 45-minute technical interviews (involving programming on the dry erase board), plus lunch. The interview is fairly challenging, so I would recommend reviewing any websites and materials that Google suggest you review, as well as maybe a combination of data structures, algorithms, and programming interview books.
I think it was difficult for me to gauge my performance in these interviews, as I got through the problems ok (with some hints from the interviewers), and the interviewers generally seem to be helpful to you. I did not receive an offer though. The interviewers were all polite, friendly, and helpful, and they all seem generally happy with the work culture at the company.
I applied through an employee referral. The process took 5 weeks. I interviewed at Google in Mar 2011
Interview
After few (meaningless) HR phone calls, a tech phone interview was scheduled. 45 min with white board coding, usually on 2-3 problems. These could be as easy as BST recursion, or as bad as skip list implementation/application. Remember your algorithms, keeping talking(it's extremely important over the phone especially the other person doesn't know if you're frowning or just thinking).
Once passed phone interview, an onsite was scheduled in around a week or so. Starting with meeting a HR to brief you about the day, you'll meet 4-5 engineers for 1:1 technical grilling. Other people said enough about google onsites, and especially I didn't make, I'd just suggest you be relaxed, trust your skills and keep communication flowing with interviewers.
Interview questions [1]
Question 1
Way back years ago, I was asked to implement the NP-hard 3-set algorithm on the spot.