Basically, you get first married in one country, and then you register the wedding in the other. You should do this registration, as is might be useful in the future (children, ...).
It is normally much easier to get the paperwork done in the country you are living in. And then register it at the Japanese embassy.
If you choose to have the official wedding done in Japan, keep in mind that Japanese authorities will ask you an official document from your own country to justify that your marriage will be legal. Such document is not always easy to get: while US citizen just go to their embassy and sign a paper attesting they are not already married, most of the countried - especially in Europe - gather several document at their embassy in Tokyo and send them back to your home country for extra checking. This takes usually a couple of months. So if you are not living in Japan, this is not an option...
sanji