I've gone as thin as 26x1.25 (Specialized Fat Boys), but currently have 26x1.5 (Kenda Rain v-cuts). However, just in my experience but to a certain point, width isn't important (I had some tyres that were 26x1.25 that seemed -at least based on rough timing -to be slower than some wider tyres I used. I guess the tread just wasn't efficient). Also factor in tyre pressure as well.
I think 26x1.5s are usually a good size, and usually offer a good selection and value (and as Kestevan pointed out, if you have wide rims, your choice may be limited anyway).