For us, the most important thing is having a roof over our heads each night and something to sleep on – if it’s cheap and available, we’ll take it. Second to this would be power outlets to recharge your batteries, and an internet connection. You’re pretty much guaranteed to get these anywhere you go, so the cheapest places are adequate as far as we’re concerned. You might lose internet once you get out in the sticks, but that won’t kill you.
Assuming you’ve got a rough itinerary planned out, you can start looking for places to stay. You should keep a rough budget in mind; you can guess most places will cost several thousand yen a night for a twin/double room (this changes if you’re staying in a single room, etc).
You can make bookings online for a lot of places, usually a few months in advance. This is a good idea if you’re travelling during a busy period. You might have to make reservations by phone at other places, try asking for an English-speaker if you’re stuck (weekdays are better for this).
If you can find a Toyoko Inn in the area, go for that. They’re a big chain so there’s plenty of them, and you can probably pay by credit card if you need it. They’re cheap, comfortable, and provide internet access.
If you’re in Tokyo, Sakura Hotel probably has a convenient branch for you. They’re affordable, convenient, and have a range of rooms available to suit different needs. The Jinbouchou branch is right next to a subway station (no JR nearby though), around the block from the building featured in Read Or Die, and about 15-20min walk away from Akiba. There’s no curfew, which is ideal for late-night sessions at karaoke or the arcades. There’s a strong backpacker vibe, and it’s very friendly (this may put some people off). Laundry facilities on-site, 24hr front desk can sell you washing powder when you need it. They also do meals, and 315yen will buy you an all-you-can-eat breakfast of cup-soup, toast, coffee and tea until 11:00.
Tokyo International Hostel is an affordable option, right on top of JR Iidabashi station (飯田橋駅) with a fantastic view out over the city. It’s a bit quieter than Sakura Hotel and has a 23:00 curfew. Rooms are dormitory-style, with a large lockable cabinet for your stuff in each room (will hold large quantities of doujin materials with no problems). Akiba is a few stops away on the JR Chuo-Sobu line, or a few km on foot. The baths are traditional-style with set hours each day. Laundry on-site, washing powder can be bought at the reception desk.
For other areas, Google usually turns up good results (eg. “hotels in Sendai” or “hostels in Matsumoto”), with plenty of user-review sites. Ideally you can find a list of places in an area, then you can check out the prices fairly easily. Some places will offer breakfast, which is convenient. Accommodation very close to a train station or airport will usually be more expensive.
Capsule hotels (usually close to train stations, in the larger cities) are an option that has achieved a certain infamy in the west. They can be a bit expensive.
A better alternative is to camp out in an internet/manga cafe (“manga-kissa”). You get comfortable chairs, vending machine food (not just drinks) and internet access (you could play some Starcraft too, kekeke). It’ s also alleged to be cheaper than a capsule hotel. One catch is that you’ll probably need to become a “member” before they’ll let you in, which means a little paperwork for a foreigner. There’s no bathing facilities, so I hope you don’t need to meet anyone in the morning.
If you’re really screwed, you can throw your bags in a train station locker and wander around the streets for the night. However, nights are long, cold and boring during winter if you’re not drinking or otherwise occupied, so this really isn’t advisable anyway.