I think one of the best things you can do is to have a web site. It can have photos of the band, a description of the kind of music you do, a sample set list (only list covers; if originals, nobody will care because they'll never have heard of them), a list of past and future gigs (with links to the web sites of those venues), and even sound clips. Pay for your own domain with a name that's easy to remember; free sites have such long URLs that nobody will bother to type them into their browser! For probably less than $100/yr., you get a really useful marketing tool.
With such a site, you can then print up some business cards with the URL, a contact name and phone #, and can hand them out to the managers at venues where you'd like to play. Be prepared to know when you're available, and how much $ you want. You can also talk up the site with everyone you know; you never know where a gig can come from. Somebody knows somebody, etc.
Then, as others have said, you just have to do a good job at a given venue, so that they'll want to have you back. My band has become regulars at one venue because, according to the manager, we're one of the few acts they've had in there that keeps our volume down appropriately. The manager always tells the bands not to play too loudly, since the place has a dinner and bar crowd which often wants to engage in conversation, as well as people there for the music, but few bands evidently pay any attention to that request, and consequently don't get asked back.
Good luck!