If you can, I recommend touring their facilities. Even if you have an unskilled eye, you can often get a good "feel" the place.
Does their cabling and facility appear neat and professional? (and are they steering you to specific "presentation" installations) Does the security, power systems and AC match up to their published specs? Does the person giving the tour seem to have a good working knowledge of the facility. (They may not be an expert, but they should generally at least know enough to know who's responsible for the gear and what not to touch.) Check the Emergency Power Off switches near the room entrances, are they covered, tamper resistant, and is there a security camera situated so that it can see the switch? (as one of the leading causes of datacenter failure, it really, really matters... I had techs that were employed for years push the button, because it turns out no one ever told them not to and they wanted to see what it did.)
I've had a hosting provider advertise "redundant" generators... when I toured their facility they pointed to one and said "that's for the Air Conditioners, and the big one over there is for the computers." (I wondered how long the datacenter would take to overheat if the Air Conditioning generator failed to start.)
As the previous poster said, ask a lot of questions about DR services, how often backups are tested and if/what their plan is for a total datacenter failure. (Fire, water damage, natural disaster. Many company spend a fortune making a single datacenter redundant, then are caught flatfooted when the facility is knocked offline)
Webhostingtalk.com can also be a good reference for reviews taken with a grain of salt. And as with any business relationship ask for and verify references.
Mark