Choices vary widely depending on your budget and location. Cheap travellers' hotels are numerous in big cities where you can get a room for less than ₹450. Rooms at guest-houses with a double bed and often a bathroom can be found in many touristic venues for ₹150-200. Good budget hotels in India are not hard to find. You can find accommodation in clean dormitories for as little as ₹50 in many Indian districts.
Most Indian train stations have rooms or dormitories, are cheap, relatively well maintained the beds, sheets, not the showers and secure. There are also the added bonus of not being accosted by the rickshaw mafia, getting your bag off quickly and, for the adventurous, you are highly likely to be able to jump on a cheap public bus back to the train station, just ask. Keep in mind you must have an arrival or departure train ticket from the station where you intend to sleep and there could be a limit on how many nights you may stay.
Midrange options are plentiful in the larger cities and expanding fast into second-tier cities as well. Dependable local chains include Country Inns (http://www.countryinns.com/), Ginger (http://www.gingerhotels.com), Hotel Orange 35 (http://www.orangehotel35....) Neemrana (http://www.neemranahotels.com), and prices vary from ₹1,000-4,000 per night. Local, unbranded hotels can be found in any city, but quality varies widely.
If your wallet allows it, you can try staying in a maharaja's palace in Udaipur or modern five-star hotels which are now found pretty much all over the country. The top-end of Indian luxury rests with the Oberoi (http://www.oberoihotels.com/), Taj (http://www.tajhotels/), and ITC Welcomgroup (http://www.itcwelcomgroup.in/) hotel chains, who operate hotels in all the major cities and throughout Rajasthan. The usual international chains also run major 5-star hotels in most Indian metropolises, but due to India's economic boom availability is tight and prices can be crazy: it's not uncommon to be quoted over US$300/night for what would elsewhere be a distinctly ordinary business hotel going for a third of the price. Also beware that some jurisdictions including Delhi and Bengaluru charge stiff luxury taxes on the rack rate of the room, which can lead to nasty surprises at check-out time.
Two important factors to keep in mind when choosing a place to stay are 1) safety and 2) cleanliness. Malaria is alive and well in certain areas of India - one of the best ways to combat malaria is to choose lodgings with air conditioning and sealed windows. An insect-repellent spray containing DEET will also help.
Dak bungalows exist in many areas. These were built by the British to accommodate travelling officials and are now used by the Indian and state governments for the same purpose. If they have room, most will take tourists at a moderate fee. They are plain — ceiling fans rather than air conditioning, shower but no tub. — but clean, comfortable and usually in good locations. Typically the staff includes a pensioned-off soldier as night watchman and perhaps another as gardener; often the gardens are lovely. Sometimes there is a cook. You meet interesting Indian travellers this way: engineers building a bridge in the area, a team of doctors vaccinating the villagers, whatever.
Don't count on having a reliable electricity supply if you aren't staying in an upmarket hotel. Brownouts are frequent, and many buildings have unsafe wiring.
Make sure to bring your passport wherever you go, as most hotels will not rent out rooms without you producing a valid passport. This is especially true in Delhi.