How to start naturalization process?

Hi all,
After I obtained the PR,I am recently getting closer to my goal which is being naturalized.As I always was dreaming of becoming a Japanese citizen.I read many things about naturalization but still I don't know is the first step.
- Since I live in Tokyo, should I call the MOJ (Ministry of Justice) in Tokyo for an appointment?
-Where is it located?
-Is recommended to go alone to MOJ or to go with my Japanese spouse?
-What do you have to prepare for the first?will they ask me any particular questions?
-How the first time visit goes on?
I would truly appreciate your replies.

A quick google search gave me a list of 56 steps to take: http://www.turning-japanese.info/p/steps.html :-)

First, you should obtain their description of the process as it will answer many of your questions. There is a form that you fill out listing information on you – where you have lived, where you went to school, where you have worked, how many siblings you have, etc. In your first interview, they will go over this questionnaire with you, and list the various documents you will need to prepare, based upon what you have written. After you have everything gathered and translated, they will schedule another meeting and interview of both you and your spouse.

Documents they will want will include a letter from a parent listing you and your siblings, all birth certificates (for you, your parents, your siblings, your children), koseki tohon for your spouse, your marriage certificate, wedding photos, diplomas, jyumin hyo, tax filings, current and old passports, bank passbooks, a letter written by you in Japanese stating why you want to naturalise, etc. You can start getting these now.

Jim and Paul , I appreciate your replies.

I checked the link you provided, here is where I am exactly confused.

These are the first three steps:

1- Find your closest 法務局hōmukyoku (Bureau of Legal Affairs) that has a 国籍課kokusekika (Nationality Section) that has jurisdiction where you live
2- Call and make an initial appointment. Should take at least three to six weeks
3- At the appointment, meet your assigned public civil servant and determine the initial paperwork to prepare

So, I need to first find closest 法務局hōmukyoku (Bureau of Legal Affairs), then give them a call asking them when I am supposed to visit them.
Here is what I want to know, when I go to the closest 法務局hōmukyoku (Bureau of Legal Affairs) in the first time, I will have to have a full interview with them or write all the details about my life...? or they will simply give you documents that I will have to prepare so that I can have the full interview about the nationality change later?

This means that I will have two interviews. First time visit to the 法務局hōmukyoku and the second one after collecting all the documents?
Is my understanding correct? Any clarification would be highly appreciated?

In the first meeting they will ask a variety of questions which will guide them in telling you what you will need to prepare. In this first meeting they will give to you the form for you to fill out and return to them along with the various documents. Over the course of the process you will meet with them maybe four or five times. After all is gathered and submitted, a final interview with you and your spouse will be scheduled.

Paul, Thank you so much for the clear reply. Very helpful.
One more question please, at least for the first visit to the houmukyoku, is it a good idea to bring my Japanese wife or father in law with me?
hontou ni arigatou gozaimasu.

You can do the first meeting on your own - if your Japanese is good, both verbal and written. If not, then yes bring your wife, or fatherinlaw - depending upon which one will be there to support you thru the entire process (attending each meeting, helping with Japanese).