I went to Japan over new year and used the following site to book digs in Japan before we left the Uk,
Hostels & Youth Hostels Worldwide - Online Bookings.
Advantages are that there is feedback on the accomodation so you can assess if its the place for you, there are generally some photo's of the accomodation and you can reserve online. There is plenty of choice for accomodation on the site.
Check out Michigan90's post in 'travel advice' with the useful website for arranging train/plane/bus travel.