The OED traces to use of “Machine” (as a means of transport) thus
5. a. A ship or other vessel. Now colloquial: a boat.
1637 T. Heywood True Descr. Royall Ship 27 Shee [sc. Pallas] hath (no doubt) raptured our Undertaker This Machine to devise first, and then make her.
1807 R. Southey Lett. from Eng. II. 155 We..embarked upon the
canal in a stage boat bound for Chester... The shape of the machine
resembles the common representations of Noah's ark.
1985 Sydney Morning Herald 27 July 67/6 He..had no second thoughts about helping to sail it—and it is a flighty, high-performance machine—in the Round Britain race.
No distinction seems to have been made between “wheels and no wheels"@ the essence was "transport", but obviously, to the average citizen, a machine was more common as a wheeled vehicle:
b. A (usually wheeled) vehicle or conveyance, esp. one drawn by a horse or horses, or other draught animal or animals. Formerly esp.: a
stagecoach or mail coach; (also) a brake, trap, or small carriage (chiefly Scottish). Now historical.
1687 A. Lovell tr. J. de Thévenot Trav. into Levant iii. 54 They make use of an Engine which they call Palanquin... This Machine hangs by a long Pole [etc.].
1759 J. Newton Diary 21 Mar. in Deserted Village (1992) 17 Went to London in the Oxford Machine.
1832 Mass. Stat. c. 75 §4 Every cart, wagon, or other machine,
drawn by two or four oxen.
1911 G.N.S.R. Tourist Guide 305 Close and Open Machines suitable for Marriage and Picnic sent anywhere with good horses and careful drivers.
1986 P. O'Brian Reverse of Medal (1987) viii. 218 The chaise lost not a moment:..the elegant black and yellow machine ran steadily north..never lacking for horses at any stage on the road.
There seems little doubt that “machine” was merely an extension of the idea of a cart, trap, or stagecoach, etc:
h. Originally and chiefly U.S. A motor vehicle, esp. a car.
1901 McClure's Mag. 18 i. 21/2 His assistant crouching at his feet out of range of the swift-flying currents of air produced by the mad flight of the machine.
1915 Sat. Evening Post 3 Apr. 62/2 The reliability of the machine was so amazing that, in seven years of business, not a single
breakdown had been reported.
1929 D. Hammett Red Harvest xv. 154 The machine that had been trailing us came into sight around a bend in the road..and unloaded its cargo of men and weapons.