As Harvey had said, local maps are good.
With regards to India we have used the Lonely Planet Indian road book which has done us proud and people say is as good as it gets.
We also had a basic GPS (Garmin Etrex). It doesn't have a base map but if you go on calle.com you can get the lat/long coordinates for towns/cities along your route each day and put them into your GPS. This proved invaluable as sometimes the maps weren't detailied enough and people didn't speak English. We had never used a GPS or had a clue what a lat/long coordinate were, but you sson get used to it. All you have to do is follow the direction that the arrow points and see if that looks right on the map.
Have a good trip.
When you get to Kathmandu check out the Dynasty Hotel, the advertied room rate is $65, were paying a fiver a night and its fantastic. The US website says dont come to Nepal but its no problem at all and very nice. Certainly a welcome refuge after spending 6 weeks in India (I'll Never Do It Again).
Harvey/Lisa - everything you said is true.