Is "first step on the way OF" the same as "first step on the way TO"?

Nope. Compare the following examples:

The first step on the way OF becoming an Australian.

vs

The first step on the way TO becoming an Australian.

The first example doesn’t make sense, does it? Only the second suggests a destination, which, in this case, is the securing of a citizenship.

Thanks @sandalman, I understand what you mean, and to me it does make sense.

The problem is that I’m proofreading an article to someone who is actually quite eloquent in English, so I am not sure of this, really.

And a Google search doesn’t help either… both forms are popular, apparently? http://is.gd/f7WtC

If anyone else could chime in, I’ll appreciate it a lot!

I didn’t say that using “the way of” in other sentences would be grammatically incorrect, just that it imparts a different meaning altogether. Taking the first example from the google search query that you provided, “the way of the master” refers to habits and approaches that people might adopt in an effort to emulate the way Jesus shared the gospel. The key difference here is that although one can partially embrace these Christian habits, the same cannot be said of citizenship! This should be your guide when determining which preposition to use.

I believe I got it fully now. Thank you my friend :)

The first step on the way to sanity is also the first step on the on the way to becoming sane.
The first step on the way to fitness is also the first step on the on the way to becoming fit.

the way of the Sufi is mystical
The way of the Dao is the way of least resistance.
The first step of reconciliation is often a phone call.
The first step on the way to reconciliation is likely to be a phone call.
The first step on the road to righteousness is to do unto others as they do unto you.
The first step on the road of righteousness is to do unto others as they do unto you.

to is usually better.

“The way of” usually refers to a method ascribed to a person, group, or organization.
“The way to” refers to a path toward a goal or destination.