My advisor was actually one of the people involved in the US News rankings for CS theory. I discussed it with him while I was short-listing universities.
Here is how they do it --
The part about asking heads of other places to rank universities is just one of the metrics involved.
They also take into consideration other factors such as PhDs graduated, funding available, number of publications, new faculty hired, citations received, etc.
So it is pretty well done.
However, here is a little tip he gave me:
Looking at the latest rankings alone is pretty useless, look at the rankings of the last 3-4 years at least to figure out trends of which depts are moving upwards and which are on a slide down (also what you want is for the dept you end up at to be ranked high in 4-5 years when you graduate -- meaning it doesn't have to be a top 10 right now, but has the potential to be there soon).
Of course all this comes only after short listing places that have people you want to work with.