I read reviews from an independent source such as forums. Good research is a must.
I also test their network speed from a few nodes (VPS are really cheap, can get one for as little as $5 a month) around the world.
Look at their network providers (Level 3, Cogent, etc) different providers have different connectivity around the world - Cogent is good in Asia Pacific while others may be primarily USA based.
Look at their SLA - if they don't have an SLA, then chances are your website might go down frequently. 99.9% guarantees your website won't be down for 40 minutes per calendar month and so on.
Server offerings - are their hardware offerings old? What are their prices? Someone offering 2 x 6 core processors for $20 a month won't be able to sustain their business, even OVH don't offer that low of a price.
Ask for any public uptime reports if they have them. Or if you find reviews on forums - sometimes people list uptime reports (rare but does happen). People usually do review their uptime.
Finally - only buy 1 month in advance. You don't want to pre-pay for a year only to find out their services are really bad.
