Japan is wonderful when it comes to traveling without prior bookings and getting a hotel on the day of arrival rarely is a problem. The expedition being when there's a local festival or event, than rooms fill up faster than you can count.
Most bigger stations have a tourist information and you can just tell me that you are looking for a hotel. They will then call hotels for you to find a place for you to stay.
For really cheap accommodations, look for specials run by capsule hotels. They can be as low as 1,500yen for a single night. The downside is that you can't enter during the day and most don't cater to women. Hostels and Guesthouses are also a fantastic alternative.
Hope this helps,