It's actually exceedingly difficult. The family registry, koseki, is steeped in a thousand years of tradition. You can't simply walk into the nearest city ward office and fill out a form.

There are also restrictions on the kinds of names you are allowed to choose, if for example you are naturalizing. The list of allowed names clearly distinguishes you and your family from "true" Japanese.

Actually only by surname you can only guess; there are some demographic distribution which some name are more common among. But this is not very accurate as people have moved around and with marriages and such, it's not always the case any more. (Japanese law still requires wives to convert to husband's in a conventional marriage.)

Source of information that often cited as is a 本籍 (honseki -- a location of where national registry is filed and hence, stored.) This information used to be required for a lot of the places (including driver's license, job application, among others) but because of this abuse, this is no longer a commonly collected information unless it is required. (And also you can change honseki, too.)