Update: Nick just sent me an email to put his great website to my attention. It allows you to enter a Japanese address in romanji and will locate it for you on Google Maps. So you probably want to try it before going through what is explained here.
Check out http://diddlefinger.com. Thanks for this great work, Nick!
Locating a place in Japan can be a real hell. As Japanese addresses do not follow a scheme that allows to directly locate a place from a street and a number, it is easy to spend countless hours losing yourself. You can ask one of the many policemen in the street, as they are used to answer this kind of request, but it is much better (and educational) if you can find the exact location yourself. We are going to see how we can do this with a few Japanese words and Google Maps.
The problems with finding an address in Japan is that there are not really streets like in western countries, and the buildings are not numbered sequentially. First, a city is divided in Ku, which are like wards. The Japanese character for Ku is 区, and it is always put after a ward name. A Ku is made is several Machi (or Cho), which corresponding character is 町. However, this character is often omitted. Finally, a Machi is further divided into several Chome or 丁目. These are numbered blocks of buildings within the Machi. After the Chome number is another one, which is the building number within the Chome. This is where things get really messy: buildings are not numbered sequencially. That is, even if you found the right Chome (which is already quite a sport), you may need to explore it entirely in order to find the right building.
So, this is not really fun. It would really help if you could give an address and get a point on the map of its exact location. Well, thanks to Google Maps, this is possible. However, there is one additional problem here: Google Maps doesn't understand Japanese addresses written in the western alphabet - submitted addresses must be written in Japanese. So the first thing to do is to translate our address in Japanese.
I assume that you have no knowledge of the Japanese writing system. If you do, then your task will obviously be easier, but even if you don't you're not completely out of the game. We have seen that a Japanese address is barely a refinement of sectors up to the building. Let's see how it works with a real example.
We'll take the same address that is given on the very informative Black Art of Finding a Japanese Address page. You can go read it, by the way. The example address they give is located in Tokyo, and is 1-22-14 Jinan, Shibuya-Ku. This is likely the format in which you will get an address written with roman characters, and if you give it to Google Maps it will bring you nowhere.
Let's analyze the address. Here, 1 is the Chome, 22 is the building number, Jinan is the Machi and Shibuya the Ku. The function of each part may even be explicitely stated, like in Shibuya-ku or Jinan-cho. Anyway, now that you have identified the parts of the address, you'd better know that when written in Japanese, they are usually in the reverse order. That is, city first, then Ku, then Machi, then Chome, then building number. So a typical template of the Japanese address will be:
City Ku区Machi町X丁目XX
Google maps can locate a place, provided you feed it with an address in this form - all in Japanese characters or Kanjis. So the trouble now is to find the Japanese characters for the city, Ku and Machi you look after.
There is no exact science for this step - I use two different methods.
Wikipedia is great when you need to find cities or wards. A Japanese city or ward has a great chance to have a Wikipedia page, in which the name in Kanjis will appear.

To find cities or wards that do not appear on Wikipedia, or to figure out how to write a Machi, you can use Google.
Go to the advanced search form and type in the name of the city, Ku and Machi. Then restrict the results to pages written in Japanese. In the search results, you will probably find a site that lists an address nearby yours in both English and Japanese. So all you have to do is to look for the little Ku and Machi characters and extract the interesting part. Here is what I got after typing the Machi, Ku and city we are looking for:

Lookit in the little red square. Can you see the "Ku" character? We can even recognize "Shibuya" before. Now we need to know if the rest of the address corresponds to what we need.
To help us doing that, we can just copy/paste what looks like an address and into a Kanji-to-Romanji converter. Paste your Japanese text in the form, select "Kanji to Romanji", and click on "Parse now". You will have the pronunciation of the pasted text written. Just refine until you find the Kanjis corresponding to what you need. Here, we know that the two last Kanjis are for "Jinan"! (which is, by the way, written "Jinnan" as Google also suggested)
And here we are! After all our investigation work, we finally can reconstruct the Japanese address. If we put everything in order, we have the following string:
東京渋谷区神南1丁目22-14
We give it to Google Maps, and we finally can locate our place! Thanks, Google!