There are a lot of different styles of hotels in Japan, and some need explaining because they are definitely different for your average foreign visitor. Here's some brief breakdowns about each I've run into.
Ryokans -- traditional Japanese hotels
Japanese Ryokans are a great way to save money, eat great meals, and see a little more of the real culture of Japan. A ryokan is basically a Japanese bed-and-breakfast hotel; a home that has rooms for travelers to stay in, with a communal toilet and bath, and usually a shokuden -- a dining area for the guests -- and a small traditional garden for scenery. Prices can range from about 4000 yen to 8000 yen, depending mainly on location and meals. Every ryokan I've ever been in, by the way, has included a TV in each room and an air conditioner; hardly traditional, I suspect, but a nice addition.
Most ryokans have signs out in front identifying them, and you can just drop in and ask if they have room for you to stay. If you call a ryokan from nearby, they will also usually send a driver out to pick you up. Larger ryokans in resort areas -- near hot springs, for instance -- may need you to call and make a reservation in advance; also, if you are traveling during the month of August, you will generally need to make reservations at all ryokans, as this is the busiest travel season of the year in Japan because of the O-Bon festivals. But most of the rest of the year, finding rooms should not be a problem.
At the front door, there's an area to leave your shoes; take them off, and switch to a pair of slippers, usually set out for you. The host will show you to your room, after pointing out the dining area and the bath, and will probably have a receipt form for you to fill out with your name and address... most ryokans will charge you at checkout (generally 10:00 am), rather than up front.
The rooms are almost always traditional Japanese in style, with sliding doors, and tatami (straw mat) flooring. Leave your slippers in the hall area, so you are either barefoot or in socks on the tatami mat floor. There is usually a small kotatsu table with a couple of mats to kneel and sit on, a closet with all the futon related bedding, and a yukata -- light robe -- with a small towel in each room; and often you will be brought hot water and tea with a pot and cup as well. If you don't look Asian, odds are that you will be given a quick set of instructions about useing the bath (which you may or may not understand), and will be asked if you need someone to lay out your bedding for you... if you go out for awhile, you may return to find the futon set up anyway.
This is a good time to ask -- if you can -- whether or not there are meals included in the stay. If they are, do eat there at least once; ryokans are a great place to experience a real traditional Japanese meal (and get stuffed to the gills). Meals will generally include breakfast and dinner (you tell them what times you prefer to eat), though some ryokans will have only breakfast... and some will have nothing at all. If there are meals at your ryokan, and for some reason you want to eat somewhere else one night, please let your host know in advance so they don't prepare a meal you won't eat.
Once you are in for the night -- that is, once you know you are not going out again -- it's time to put on the uniform: strip down to your undies, and put on the yukata robe. It's perfectly okay -- and expected -- that you wear the robe anywhere you go within the bounds of the ryokan, and most people will be wearing these robes during any meals they have there.
Two more things; first, guests are expected to bathe at night sometime before hitting bed... it would be rude to get the dust from your busy day on your host's bedding! Secondly, when using the toilet, you need to leave your house slippers in the hall outside the toilet room and slip on the special bathroom slippers that should be just inside the door. Don't get these confused!
Other than this, just remember that the ryokan is somebody's home that you are visiting... behave approprietly and respectfully, and have a good time.