Dr. Who?
You are going to graduate school to learn. Therefore, your number one concern should be the other end of that process -- who's going to teach you? Because you will be working closely with many of your professors, especially if you are writing a thesis or dissertation, you should find out who's who in the departments to which you are applying.

You should find out who the major players are in the department, what their research involves, what they've earned their degree in, where they are published, what their reputation is, and where they earned their degrees. From there you should evaluate if you think their research would be relevant to your interests, and if you think you want to work with them and contribute to their findings -- or would you be better served elsewhere?

Try to schedule an interview with the faculty members you are most interested in working with. This can give you some insight on the program itself and the dynamics involved in the department.

Talk to the Students
An important and easy way to gauge whether or not a department will work out for you is by talking to the other students who are a part of it. Do they enjoy working with their professors? Do they feel they have been given enough guidance and opportunity to develop their own research? Are they pressured to follow certain methodology? What are the good points and the bad points of the department and the school?

Research Facilities
Since you will be spending much of your time doing research, you should check to make sure that the institution has adequate facilities for your particular needs. What kind of labs do they have? Are there restrictions? Is the equipment up-to-date and easily accessible? Do they have an extensive library and library exchange program?

Environment
The physical location and environment of the school are key to the evaluation process. If you plan on spending the next five years studying marine life, you probably do not want to attend a school in Arizona. Also, you want to make sure that you have the amenities that you will require outside of your academic life. Are there opportunities to socialize? What kind of community will you be in?

School Curriculum
You'd be surprised at how often this is overlooked. While much of your time may be spent in research, the first year or two of graduate school involves regular coursework. You want to make sure that the classes offered are relevant to your interests and will give you some background for your research.