[samurai007]

If you will be staying in fairly large cities, you can just look for a place when you arrive. Even if your 1st and 2nd choice are filled, you'll always be able to find SOME place with vacancy. I did this in Hiroshima, Fukuoka, Nagasaki, Matsuyama, etc without any problem, though if you travel in the peek season it may be tougher.

If there is a specific ryokan/hotel you definitely want to stay at, or you're staying in a more remote or exclusive area (on Miyajima Island or another popular spot, in a small town, etc), then you should try to make a reservation.