How common are interviews for Computer Science PhD programs?
Extremely uncommon

I understand that interviews are fairly common in other fields and in other countries, but they are rare in computer science in the US. In my experience (student, postdoc, or faculty at five different American CS departments; multiple years on graduate admissions committees; dozens of recommendation letters for CS undergraduates applying to graduate school), very few (if any) American computer science departments include interviews as a standard part of the PhD application process.

There are rare exceptions, though, usually involving prospective advisors calling up applicants directly.  The most common reason for a phone interview in my department is to assess their English fluency, especially when the applicant's test scores are borderline, or there seems to be a discrepancy between their test scores and the fluency of their statements.  I'd be surprised if this happens more than 10 times a year, and we get 2000 grad applications each year.

When I applied to Berkeley's PhD program, I was already a PhD student at UC Irvine. My future advisor and the director of grad admissions called me to ask why I wanted to move when I seemed to be succeeding in my current program (good advisor, good research progress, and so on).  I suspect they also wanted to understand the discrepancy betwen my grad school grades (good) and my undergrad grades (terrible).

In short, as long as there's nothing borderline or non-standard in your application, it's unlikely that you'd need to be available for an interview. And even if someone does want to interview you, they're much more likely to want to do it by phone or skype than in person.