Kazinka,
I think it totally depends on your situation at each interview. If you are the kind of person who would feel really uncomfortable staying with random people, or like another person posted, you have a really late flight or something, staying with graduate students might not be for you.
I will also mention that I've read a LOT about interviews (if I ever get one, I think I'll be REALLY prepared), and a lot of people recommend staying with students the night before because most of them will be really helpful and give you an idea of what you're about to go through, or what to watch out for.
Good luck to you on your interviews (whoever you stay with)!