Here in Beijing, there is (normally) a woman standing at a little desk on the way out of baggage claim for domestic flights selling SIM cards. Depending on your need, I think they cost either 50-100rmb. In the international terminal, you can find SIM vending machines that present options from the three main service providers, but I am fairly certain it only accepts rmb.

You can get 3G service from China Unicom, offering something like a pay-as-you-go plan. They require a passport to register. My plan for my iPhone (2gb/month plus 500 minutes and unlimited text) is about 200rmb a month.

You can also pick up a ChinaMobile (recommended for Edge) or ChinaTelecom card from most magazine stands and also from shops close to hotels and well as from the ChinaMobile/Telecom/Unicom stores that you can find all over the place.

Also, buy the card in a major city. The cards are often regionally locked and will not always work if purchased in another city. Wuhan cards are an example.