The interesting parts of the Google interview process are all under NDA, and you can't discuss them for two years after the interview. Here's what I can tell you:

• Their initial contact with me was via email, through LinkedIn. I didn't contact them.
• Two rounds of telephone interviews are required for out-of-state candidates (i.e., anyone they will have to pay to fly in). Both interviews will have a "take-home assignment" portion: a piece of code you'll have to write and email to your interviewer within a fixed time (1 hour for me). If you pass these hurdles, you'll be brought out to Mountain View for an all-day in-person interview.
• Travel arrangements are absolutely painless; it's all handled for you, and all you need to do is write an email and pick dates.
• Google flies you in on Day X, interviews on Day X+1, and flies you out on Day X+2; no redeyes are necessary. They pay for flights, hotels, rental cars, and per diem for meals. You get to pick airlines and rental companies for frequent flyer miles. Note that you have to put your meals and the rental car on your own credit card and file for reimbursement. They say to allow several weeks for reimbursement, but my experience was that the money arrived by direct deposit in about a week after filing. If you wish to stay extra days to explore the neighborhood and pay for the additional rental car and hotel expenses yourself, that's fine.

The interviews are extremely technical and involve real programming exercises, manipulating data structures, analyzing or describing algorithms, etc. Be prepared to iterate what you're doing on the board. Be ULTRA prepared with knowledge of standard search and sort algorithms and junior-level CS data structures; also be aware of their big-O complexity. While the interview questions aren't exactly complicated, they cover so much territory that there is no way to study for them from "cold." If you are not programming on a daily basis in the languages in which you're being interviewed, you will not pass these tests.

The process moves extremely quickly, at most a day or two between steps. Depending on how your scheduling works, you could go from first contact to an offer in less than two weeks.

Absolutely everything you have read about Google perks and benefits is entirely true. It's hard to imagine a company with better employee benefits.

Interview questions are protected by a non-disclosure agreement.