Apart from the criteria mentioned by AdolfinWolf, I also look at that exchange's history:
- whether it was hacked or involved in controversy,
- how they reacted to unfortunate events (hacks, crashes etc.)

You could also check whether they are:
- friendly to hard-forks
- distributing GAS (if you are the NEO type) etc.