Comp Sci PhD Admissions: How often are Skype interviews requested?

Time is one of the most valuable resources for professors – I know no one who just offers interviews for fun.

Should I be very encouraged or is this standard procedure for almost all qualified applicants?

Be very encouraged. I can guarantee you that they don't do it for all "qualified" applicants, because nobody has the time to do that. In my institution in Sweden, for any given call, we may get somewhere between 25 and 150 applications. Even of only a third of those are qualified, it is easy to see that the hiring faculty member can't interview everybody who is qualified even for a call that received comparably little attention. I typically interview about 3 to 5 people per call, and I would presume that this is fairly normal.

That said, take the call very seriously. In the past I have been highly disappointed with how badly prepared many applicants were in these Skype calls (e.g., I usually ask beforehand that candidates do a short 10-min presentation of their master's thesis and some candidates have no presentation prepared, or candidates who have obviously not even looked at my website and clearly have no idea what kind of research I actually do). I never hire applicants that seem ill-prepared for the interview.