To begin a journey or project. In the original meaning, "way" had a specific nautical meaning: "forward progress of a ship though the water" (or the wake that the ship leaves behind). The usage continued into the 20th century and was used in aviation as well as shipping.
In the original term, "under" also meant "on the" and presumably migrated to "under" from the influence of the Dutch word onderweg (meaning "underway" itself, but which probably sounded like "on the way" to English-speaking sailors). At some point, it was also erroneously believed that the correct spelling was "under weigh," meaning not anchored and making progress through the water.