I lived in India for over a year and did not have too difficult a time being vegan there. Here are some key points:
1) Almost all Indian desserts will have some form of dairy in them. Jalebis, an orange-colored, fried sweet dough, is the only naturally vegan Indian dessert that I know of. Sometimes you can find sweet shops that sell little nut-based candy things (made out of cashews and pistachios, typically) that are occasionally vegan, but not always. Make sure to ask about butter and ghee, in particular.
2) The vast majority of South Indian food is naturally vegan; items with butter or ghee are usually labeled as such on menus, because they're more expensive to make at restaurants and are priced accordingly. Typical South Indian offerings include masala dosa, uttapam, idli and sambar, cutlets, etc.
3) Indo-Chinese dishes, often times called just called "Chinese" on menus, are always vegan, such as the ubiquitous veg. manchurian or gobi manchurian.
4) Street food is a mixed-bag. Some items you can tell are obviously vegan or lacto, but some are not as straight-forward. Pav Bhaji (bread rolls eaten with a stew of tomatoes and vegetables) is usually made with butter on big skillets. Vada Pav (popular in Bombay and Pune), a potato dumpling in-between a roll, is vegan.
5) North Indian food is the most difficult of all. Typically, it's made with some type of dairy. Dal Makhani/tadka (cream or ghee), tikka vegetables (yogurt), vegetable korma (yogurt/cream), jalfrezi (cream), and various curries all use cream or yogurt. Simpler North Indian dishes, such as aloo gobi (potatoes and cauliflower) and channa masala (chickpeas), are almost always vegan, or can be made vegan. The best thing you can do is specify "no yogurt, cream, butter, ghee or milk." Tell them that VEGETABLE oil is okay, though.
6) Naturally vegan Indian breads are usually chpatis, rotis, puris and poolis; no one will put ghee or butter on them either, unless you ask. Naan is never vegan (yogurt is used in the mixing preparation). Parathas can sometimes be vegan, sometimes not.
6) Soy milk in UHT/tetra-paks is becoming more easily available in upscale groceries, and even mid-range groceries, in mid-to-large sized cities.
7) In some cities, such as Pune and Nagpur, one can find locally-made tofu and soy milk at numerous stores.
8) Nutrela is a widely-available brand that makes "soya chunks," which are dried pieces of soy that become spongy and meaty in warm water, like texturized vegetable protein or gluten strips. If you can't find tofu, this is a good substitute.
9) Some chain coffee stores like Cafe Coffee Day, are slowly starting to incorporate soy onto their menus.
10) When ordering tea, make sure to specify "no milk" or simply say "black tea." Ask for lemon/lime on the side, as well as sugar, as Indian black tea tends to be extremely strong. Tea at roadside stalls is always pre-mixed with milk and you can't get modifications, but at mid-range restaurants and above, it's no problem to ask for black tea.
11) When in doubt, just ask questions! If the waiter doesn't understand you, then try to find another patron who can explain your dietary needs in the local language.