National Archives of Japan Digital Archive, Digital gallery
http://jpimg.digital.archives.go.jp/kouseisai/index_e.html
This site has among other things, the complete "Tempo Kuniezu"天保国絵図," the maps made of the whole country 1835-1838. The link is to the English area of the site, though the maps themselves are of course in Japanese.
[Japan] Geographical Survey Institute maps
http://watchizu.gsi.go.jp/
This allows searching by name as well as by location and latitude and longitude.
These are extremely detailed maps, in fact, so detailed that it can be hard to figure them out even if you know the area. They are probably best used after getting oriented with some other maps. It is Japanese only.
Yahoo Map Information (Japanese)
http://map.yahoo.co.jp/
A very popular commercial site (i.e. LOTS of advertisements). It alows searching by name and place. I have found some historically related places by name here that were not on the gsi site. It is especially convenient it that one can easily change the scale and also switch back and forth between maps and satellite photos.
National Diet Library Catalog (English)
http://opac.ndl.go.jp/index_e.html
The NDL has a map section, and it can be searched by going to the "Search for General Materials" link and checking off "Maps" near the end of the list that starts off "Books (Jpn.) Books (Foreign) Periodicals ".
FreeMap
http://www.freemap.jp
http://english.freemap.jp
Clear, basic maps of Japan, East Asia, and World, available blank or with prefectures, labeled or unlabeled. Also, a keen option to customize areas by color for the purpose of demographic displays or the like (or to help show the spread of the control of certain powers within a given time...)