Yeah it's fairly easy. You just approach the bar or venue where you want to perform and ask if they have an open slot for your band (usually you need to gove them about 6 weeks notice as most organized bars will arrange their event schedule at least a month in advance). Many places will be willing to let you perform as the opening act together with a few other more established bands. However, don't expect to get paid for this or to land a weekend gig. Bands that are unknown and just starting out tend to get slots on Wed or Thurs evenings more easily but if you manage to attract a large audience or fan base, venues will take notice and let you play on more popular nights. So I guess the first step is building up credibility and a fan base.

Damn you, coffaholic, for providing such a perfect answer on a subject I knew well!

But yeah, what he said. Also, what also got my band a few extra gigs was simply when we were walking around with our instruments on our backs (I often carried my guitar around). Sometimes some people would simply come up to us, ask what we played, and then proposed us to play at their bar.

If you're in Beijing, try starting out at the What Bar,  the Hot Cat Club or Mao Live House, they're usually rather kind to new bands, but expect to be asked to play during calm week days. If they find you good enough, they'll probably ask you to play again. Then, as coffaholic said, you get some reputation, and it gets easier and easier to find gigs in other places.

I gig with local bands, usually at corporate events such as indoor dinners at hotels or outdoor grand openings (supermarkets, real estate companies, etc.). Caveat: gigging is illegal if you do not have the proper work permit and you risk arrest. I know a couple of foreign musos who got hauled off to the police station, passports confiscated, had to pay a huge fine to retrieve their passports, and got off with a warning not to violate the visa regs again.

Maybe playing in a bar or cafe is safer, but I doubt it.