For me, I did not consider research fit as the most important. I figured that as long as I did not hate a topic, I would be happy pursuing that. After all, you don't finish 5+ years of working on your PhD thesis without getting tired of it! So, instead I weighed the following things equally:
1. Interesting research available--I was not looking for a perfect match between my interests and what the school had to offer. I just wanted to know that there would be something/someone I would be interested in working with/for.
2. Program fit--I want to make sure I got along with the current students as well as the others in my cohort. I also wanted to be in a place where the professors and students get along and have common goals. And, I wanted a place where the school treats its grad students well and values us as employees that do good work instead of seeing us as a source of expendable labour. Finally, I wanted to be in a program where the goals/requirements/courses matched my interests.
3. Location--I wanted to be happy and feel safe about where I was living. I did my Masters in a small town in Eastern Canada which made us pretty miserable (too cold and not enough diversity). Also, it needed to be a place where my spouse could find work.
4. Financial stuff--The stipend had to be high enough that it was worth going to grad school for. Obviously, we don't expect to make a ton of money as grad students, but I wanted to be in a situation where I did not have to worry about money constantly. The stipend had to be high enough so that with proper budgeting and planning, we should be able to live comfortably (not in luxury or anything, but I don't want to be living in a tiny apartment eating ramen!).
Even though I numbered these, I really did treat them all equally. My spouse (not a student) and I had equal say in where we moved and we both picked the same place (she visited some programs too).
In order to get the information to make the decision though, I really think visiting and going with your gut feelings is really important. A Skype meeting can be an okay replacement but you can get so much more information out of a full face-to-face interaction, such as reading body language but also they can show you things on a computer or a piece of paper etc more easily.
Factors 1 and 2 (research + program fit) can be determined by asking questions to profs, especially the academic advisor for question 2 (find out if you get electives, how many courses to take, how long to finish all courses, what are the comps/quals like, how many exams are there, what is the approximate time to finish).
Ask the same questions about the program to grad students too, and get their perspective. They will have a different view of course, but if the two are vastly different, then there might be a communication issue between department's expectations and what the students think is expected.
The research aspects can also be determined by looking at the paper output (as suggested by the above). In addition to total count, you can also look at the author list/author order. Does the group let the grad student publish as first author? Also, look at the quality of output. Are students working on new/interesting/original problems that can get them jobs later on in their career? Or, are the students just doing standard analysis and are just acting as "cogs in a research machine". My undergrad supervisor said that in picking your PhD topic/group, the most important part is not that you like the research, but that you think other people will like the research in 5 years, when it's time to get a job.
Factors 3 and 4 (location, financials) is best asked to grad students too. Ask them what the cost of living is like, and if they feel their stipend is enough. Ask them about the area and how they like living in the current place (ask them where they used to live, for comparison). Find students in the same situation as you (international? American? single? married? spouse also looking for work? have children?) and find out what their life is like at the school.
Finally, there are some things you can/should do some research on. I read up about each of the cities. Wikipedia has useful average weather data. I read about major events that happens in the city and some news stories (but be careful to get a representative sample) to see what the city is like. I also use PadMapper or something similar to get average rent prices for the kind of place I'd want to live in and then compare that to the stipend offer and see if it's enough. For me, the cost of health insurance for my spouse was important as well.