What is the origin of "on the way"?

A brief look in the OED doesn't find speed as a nautical meaning of "way"; it would seem that definition II.6, an unobstructed passage, is more apt. All of the definitions in II ("course of travel or movement") give us the connotation for the meaning of "on the way," a locution which the OED notes has come down to us from the Old English on wege.

The OED does mention the nautical sense of 'way' at 7i (italics mine):

Naut. Progress (of a ship or boat) through the water; rate of progress, velocity; impetus gained by a vessel in motion.

A speculative see-also under the definition reads

Cf. under way at sense 38a (38), from which this sense was perh. evolved.

intimating that the nautical sense may have evolved from the sense at 38a, which includes the phrase you asked about:

under way Naut. [ < Dutch onderweg (also -wegen) on the way, ...

The earliest quote in the OED exemplifying this latter use is from 1743:

1743 J. Bulkeley & J. Cummins Voy. to South-seas 98 To prevent which, we do agree, that when Under-way they shall not separate.

The earliest quote exemplifying the former nautical sense of 'velocity, rate of progress', is, however, from 1663:

1663 W. Davenant Siege of Rhodes II. ii. i, Those who withstand The Tide of Flood..Fall back when they in vain would onward row: We strength and way preserve by lying still.

Now, the sense of 'in the course of a journey' is given in 36a:

on (or upon) the, or one's, way : on, or in the course of, a journey. ...

where the earliest quote exemplifying the use is from c1000:

c1000 West Saxon Gospels: Matt. (Corpus Cambr.) v. 25 Beo þu onbugende þinum wiðerwinnan hraðe þa hwile þe ðu eart on wege mid him.

Note that on wege is Old English equivalent to the present day English phrase 'on the way'.

The nautical sense of 'way' as velocity and the sense of 'way' as a journey arose from the same roots. However, the nautical sense arose at a much later time and appears to me to have been sponsored by the 'journey' sense, rather than the other way around.

Edit:

I wasn't aware at the time I wrote the above of the casual folk etymology (perhaps arising from the heedless speculative interjection in the OED) ascribing the origin of the phrase 'on the way' to Dutch onderweg[en]. Even after becoming aware of that casual etymology, I did not take it seriously: the notion does not match up with the textual evidence in hand. The quote from c1000 of the phrase on weg predates the earliest quote exampling Dutch use of onderweg in the sense of 'under way' by somewhere around seven centuries, after all. And that objection says nothing of the extraneous complications arising out of the muddled chronology in which the Dutch use of onderweg is bound up with 'under' (onder, that is, 'on the') as used in the phrase 'under sail'.

However, being of a curious and stubborn nature, I cast about (not 'came about') looking for any additional evidence that might support the rather remote possibility that the sense of the phrase as given by the OP ('in the course of a journey') had some nautical origin afterward reflected in the Dutch appropriation and purportedly hard of hearing sailors' nautical transference of that appropriation to 'under'. As usual, the simplest and most straightforward interpretation of the evidence remained, to all appearances, the best.

I did find others than myself worrying the nonissue. At Grammarphobia, in an entry dated March 19th, 2009, I found reasoning closely paralleling my own as set forth above this edit. In particular, the following about the quotes found by the OED scholars regarding the 'underway' term from Dutch onderweg:

The chronology doesn’t seem right, however, since published citations for “under way” are all more recent than those for “way” in the nautical sense. But “under way” might have been in use for years without making it into print.

Years in use without making it into print, yes, but probably not the seven centuries it would take for 'underway', however bound up and confused with a nautical sense of 'on the way', to take a central or otherwise prominent spot as the origin of the phrase 'on the way' in the sense of 'in the course of a journey' as found in the Old English phrase "...on the way with him" (translation of the OED quote c1000), a phrase equally if not more likely to "have been in use for years without making it into print"--especially considering the comparative scarcity of any sort of print c1000.

Still not satisfied (curious and stubborn to a fault), I kept looking until, after a brief flirtation with a Romanian encyclopedia compilation website that had the annoying habit of changing from English to Romainian at fairly rapid intervals, I verified that onderwegen means, literally, 'under or among the ways', and wegen means, as expected from all the evidence I'd already examined, 'roads or paths'. Thus, even supposing against all available evidence that 'on the way' originated as a 17th century sailing terminological corruption of onderweg (meaning 'underway'), the origin of onderweg must be refered back to its literal (that is, minimally metaphorical) nonnautical sense of 'on the road, path'.

I'd answer this by considering the same or similar usages in other sentences, such as:

"On the way home, we saw a fox."

Here there is no indication at all of speed or haste. Seeing the fox was an incident that happened during the journey, and so here the term way is defined as the path or route travelled, for example, "Is this the way to Amarillo?"

Another example, more closely to your initial post:

"Where are you going?" "We're on our way to the Emerald City."

Again, it's obvious that way shows no indication of the speed of the journey, but is directly referring to the journey itself. Therefore your example of "on the way" is the path definition, not the nautical definition.

Way seems to mean, at its most basic, a course. To "make way" or make "headway" is to progress. When you are on your way home, you are on en route and are literally on a course for home. The Online Etymology Dictionary says that the term "underway" was first used in 1749 in reference to ships having begun to move. This supports the nautical origin because movement is related to the way as in speed. However, in as early as 1550 the phrase "one way or (the) other" was used in the sense of a route, or course. From this I think that the nautical sense of speed or movement came from the older meaning of way meaning course. It makes sense that the modern phrase of "on the way home" comes from the non-nautical meaning because you using "way" as a noun that you on, i.e. a route. The nautical way is something you might need to engage the rudder but does not seem related in grammar or meaning to the current meaning of the word.

By the way connotes the speaker's narrative is an idiomatic journey, hence the use of the word 'way'. The added information is something you would generally 'see' on the 'journey' of the speaker's topic.

The german word for road is Weg, and in Danish it's Vej, and both sound a lot like the english word Way. So my guess is that, that's where it originate. So some common word for road used or influenced by these countries.

We have the exact same expressions "look the other way", "going seperate ways" etc. in Danish as the English terms. If you replace way with road, the expressions still make sense: "look (to/down) the other road" or "going seperate roads". But that is just my guess, I have no historical data, other than I speak both Danish and German.