For us, we had the customers BEFORE we opened the business. As a web host you are almost required to align yourself with web designers and have them drive the business to you (at least initially). Starting out, I'd suggest contacting local web developers in your area, and setup an arrangement where you would refer work back to them etc.
Also, it's important to note that you must ASK for the sale, from EVERYONE. You'd be surprised at how many people want web hosting but don't know where to go. They then remember something they saw in a paper, and signup. It's your job to get them to come to you - get your name out there!