Buddhist temples (called o-tera in Japanese) and Shinto shrines/temples (called jinja in Japanese) may also maintain some family records. Many Japanese families partake in facets of both religions depending upon the occasion. Weddings often seem to contain elements of and references to the Shinto religion while funerals quite often center around Buddhist rituals. (Please realize this is a generalization. Christianity and other religions exist in Japan. You'll want to ask your elderly relatives what religion they are or what religion their relatives were.)
Begin researching temples by narrowing down your search to o-tera or jinja which are located in or around the area where your ancestors lived. If your ancestors came from a large city, you should try to narrow your search down to o-tera or jinja located in the very near vicinity of their address. Smaller villages generally only have a handful of o-tera or jinja in the area, a fact that automatically decreases the research necessary. The down side, however, is that these temples won't likely host pages on the Internet whereas some of the larger temples in big cities might. If you know the name of the temple or shrine your family may have been affiliated with, write to the priest. If you can do this in Japanese it would be helpful. Though I do not know the specific rules, the priest may be able to share information with you.
The records that these religious organizations may maintain are different however from those maintained by municipal offices. Funerals and the concept of life-after-death are often based in the Buddhist religion. Jeff Morita was kind enough to point out that the records obtained from Buddhist temples may require lots of extra effort to understand. Some of the records held by Buddhist temples may record information about deceased ancestors. Soon after a person's death in the Buddhist religion, their spirit is given a new name. This posthumous name is referred to as kaimyou in Japanese. This posthumous or spirit name (kaimyou) will not be the same as the name your ancestor used while they were living. (Feel free to correct me if this is wrong.) The posthumous spirit name however might, might, include some of the kanji characters from the name they used while they were alive. The records that the temple maintain may often refer to your ancestor in terms of their posthumous spirit name rather than the name they used while they were living.