Road Maps
Normally bicyclists will profit by buying the most detailed maps they can find; I sometimes use 1:86,000 for detailed route planning. However, as the Japanese love to build roads (or, to put it another way, since Japan has a very powerful construction lobby), any map you buy is likely to be a bit out of date. Therefore, currency must also be a major consideration. Most maps sold here are 1/200,000 (for those that include Hokkaido, this often changes to 1/300,000 for the Hokkaido portion), and these should be good enough for most route planning.
There are also other considerations that may be more important where the rubber meets the road. One is elevation; try to find a map that has elevation markings right on the road as opposed to only on high peaks beside the road (not all maps have the markings right on the road). This beats trying to figure out the elevation squiggles on the map, and wondering whether how close the road gets to the elevation of that nearby 2,000m peak. Another is, of course, linguistic. One of the advantages of the "Max Mapple" series described in the Road Maps section is that, even though this is a Japanese map, major (and sometimes quite minor) city and area names are also shown in roman characters (romaji) as well as in Japanese. Therefore, even if you don't read any Japanese at all, you can use an English-only map to do your general planning and take the Japanese map pages for detailed on-the-road checking to make sure you're on the right road. I strongly recommend that you take along a Japanese map, partly for the greater detail (there's nothing harder than trying to figure out whether that Chinese character on the sign at the fork in the road corresponds to anything on your English map... ) and to make it easy to ask for directions if you need to do so.
One other advantage of the Touring Mapple guides: they show the locations of Toho-yado inns, youth hostels and even some "rider houses" on Hokkaido.
For other reference materials that you may find useful in route planning, see RESOURCES.