I've just got an airtel sim card, and the process was similar to how rlesko described. Short answer is that for Airtel, you need a recent-ish passport photo, a photocopy of your passport details page, a photocopy of your visa, a photocopy of something official with your home address on, and the originals. Should take about 30 minutes to get the sim card and have it work, add another 15-30 for 2G internet.
As things differed slightly to @rlesko's case, I'll let you know how it went for me so you've another data point. Before heading to the store, I got a photocopy taken of my passport details page, and of the visa page, and ensured I had a recent-ish passport photo. What I didn't have was anything official about where I was staying, or my home address. This proved to be somewhat tricky.
When I got to the shop (a small independent Airtel dealer), the owner was a little reluctant to sell me a prepaid simcard, as he though it'd be a lot of work and I wouldn't have the documents needed, but with the help of the taxi driver I convinced him I had all the required copies and originals, so he relented. He checked the copies and the originals, then we hit a snag. He wanted my home address from my passport, but a UK passport doesn't have your home address in it. I offered my driving license, but that wasn't what he was expecting. The passport did have the emergency contact details for my family in it, so the eventual solution was to nip a few doors down, photocopy that page too, and then put my parents address from the contact details on the application form... I think it would've been easier with a photocopy of my driving license to start with perhaps, or maybe a letter from the hotel confirming I was staying there so I could have used that address as the home address. Putting the hotel address down as the current address wasn't a problem, and that bit wasn't checked.
Having got the copies in order, there was a form to be filled out, with some confusion as my passport doesn't have my father's name on it, which was a required field, and the addresses weren't in the right format. Eventually got that sorted, signed the form and copies, and the SIM activated quickly. Got a hard sell on the amount to top up, basically wasn't allowed to go for the cheaper ones, but nothing too unusual there as a foreigner. The shop owner ensured I could make a call and the topup had worked before I left, then added 2G internet for me by text a little later. It all works, and I can text, call, and I'm posting this on 2G!
During all this, people were coming in and topping up their phones, which involved saying their number, it was typed into a phone, they checked, text came through to them and the shop owner, then they paid and were gone. Seemed quick enough! But did delay the sim card buying a bit as we kept stopping so that topups could be quickly sold.
