Below is a short list of tips and thoughts regarding the Google interview process that might be helpful to anyone interested in interviewing with Google -- but (as LeVar Burton would say) you don't have to take my word for it -- I didn't get the job.

1. Know Someone (Networking): Like I had mentioned, I believe the statistic was that 1 million resumes were sent to Google but only 5000 people were actually hired last year. From that perspective, that means if you apply to Google, you have a .5% chance of actually getting hired. If you know a Googler who can refer you, the recruiters will most likely consider you before they consider a random applicant. Going through a referral will get you noticed quickly. From the time I was referred to the time I was contacted by the recruiter was a matter of days.
2. Dont let this be your first interview in a long time: I'm copying this word of advice from a current Google employee who wrote a blog entry about interviewing and I can definitely agree. He said do not interview with your dream job first. If you are a bit rusty, you may have trouble interviewing at your 'dream job'. I think that was one mistake I made. I think after interviewing with Google I became a bit more refined in how I handle myself, what my career goals are, how I talk. Interview with other companies, let your thoughts, opinions and skills really sink in and then have a go at your dream job.
3. Hammer down on the fundamentals: The recruiter will probably tell you this, that at Google algorithms and data structures are the 'bread and butter'. The interview will most certainly center around problem solving using algorithms and data structures. Given certain conditions, ie memory, environment, language, etc, what would be the most efficient way to solve a problem. Know your basics and be prepare for the twist. Old text books and even the AP Computer Science book are actually a great resource because they do just that. The chapter teaches about the topic but the question section always puts a tweak and presents a unique problem.
4. Paper and pencil coding: As I prepared for the interview, I tried to code out problems on paper and pencil to mimic the actual interview process. I soon realized how much I relied on the IDE to help me code. There are so many things the IDE does for the coder that I was just kind of mentally screening out such as certain syntax or structure. Do your best to code using paper and pencil because that's definitely what I experienced.
5. Talk a lot: I don't mean be annoying and just babbling, but speak your mind as you grind down into an algorithm or a problem. This shows a thought process and gives clues to the interviewer about your skills and personality. I believe the interview is meant to be somewhat of an exchange between the interviewer and interviewee. By keeping open, intelligent dialog, I think I was able to get through my questions much easier and even get help from the interviewer.
6. Be prepared for a long process: I can't say this for sure (since my interview process ended rather shortly) but from what I understand and what I was told, the process lasts more than a month. With the myriad of interviews and reviews, the length of time is no surprise. Fortunately it just gives the interviewee more time to study and sharpen up.
7. The interview process isn't always an accurate representation of a person: After having gone through what I have, I've been able to at appreciate what Google is trying to do. They are trying to produce the most effective interviewing process laden with tough questions meant to bring in the best of candidates. It seems to work, but at the same time an interview may not best represent a candidate. I know of interviewees who are bright, capable, technically strong and interpersonally gifted who did not get the job, but this just shows the arbitrary nature of interviews, which brings me to my next point.
8. A bad hire is worst then screening out a good candidate: Anyone who has ever worked knows just how much a bad hire sucks the life out of an organization. A phone screen is named as such to show that it is meant to 'screen' out people who aren't a good fit. This interview process is so rigorous that bad hires presumably do not make it through. Unfortunately at the same time, the rigorousness will screen out some great people, but the ones who make it through all have a strong chance at actually being great employees.
9. Contract to hire is good: From what I understand, a lot of the new hires are being brought on as a contractor before being hired full time. This is a really good idea in keeping the integrity within the organization's engineers. The probational period is just another screen to make sure candidates really do meet the needs and requirements of the company. If you make it far through the interview process, this may happen to you.
10. Have Fun: So I didn't get the job, I never got to experience the free world class dining, the trip to Mountain View, or the subsidized massages, but through it all I'd say it was a pretty wild yet short ride which I enjoyed. If you are a software engineer and you are applying to Google, there must be a part of you which is genuinely interested in challenges and problems. There must be a part of you that gets geeky over these kinds of things. Go into an interview and do your best to enjoy and have fun in the moment. If you get it then great. If you don't then hopefully you gained something from it and enjoyed the thrill whatever the outcome -- I did.