The 1908 edition of the OED has this entry (unchanged in the 1971 edition of the OED) for man-of-war:
Man-of-war Pl. men-of-war {in sense 1 app[arently] after F. homme de guerre; for sense 2, cf. MAN sb.1 12.} 1. A fighting man ; a soldier, warrior. Obs[olete] exc[ept] arch[aic] or jocular. ... 2. A vessel equipped for warfare ; an armed ship belonging to the recognized navy of country. [Earliest three cited occurrences:] 1484 W. Cely in C. Papers (Camden) 144 As he cam to Callez wardd ij [that is, two] men of warre of Frensche mett wt hym and fawght wt hym. 1594 Glenham's Newes fr[om the] Levane Seas in Collier Illustr[ations of] Old Engl[ish]. Lit[erature] (1866) I.4 In sight of the King of Spaynes men of warre, which were twenty two sayles. 1680 Debates in Parl[iamen]t (1681) 120 It {Tangier} will always be Serviceable, as well for our Men of War to resort to..as for the protection of our Merchant-men.
A fairly early instance of "men of warre" in the sense of "ships" (not mentioned by the OED) appears in a 1579 translation of Synesius of Cyrene, A paradoxe, prouing by reason and example, that baldnesse is much better than bushie haire, &c.:
Forsomuch therefore as I haue the more excellent cause to defend, notwithstanding my cunning be not counteruaileable vnto Dions, whie should I not make readie my selfe, according to the equitie of my cause, to praise Baldpates, and to dispraise such as are loaden with hairie locks? And for entrance into my matter, I néede no curious or vehement beginning, which I am content to leaue vnto Oratours, as properly pertinent to their earnest cases, wherwith they geue strength to their present purpose, arming it (as it were) against the aduersarie, as the shippes (called men of warre) are prepared against the enimie.
Another early instance appears in a 1588 translation of Juan González de Mendoza, The historie of the great and mightie kingdome of China, and the situation thereof togither with the great riches, huge citties, politike gouernement, and rare inuentions in the same:
At the end of the two leagues, there whereas the Captaine did leaue the companie of our Spaniardes in the riuer, they came vnto a great baye, whereas was at an anker a fléete of more then a hundreth and fiftie shippes men of warre, whose Generall was this Captaine, whom we haue spoken of, that did beare the Fryers and the rest companie.
The relevant portion of the entry for man, cited near the beginning of the OED entry for man-of-war at the top of this answer, reads as follows:
Man sb.1 ... Transferred uses. ... 14. With qualification used for : A ship. See also MAN-OF-WAR, INDIAMAN, MERCHANTMAN, etc. [Earliest three cited occurrences:] 1473 J. Paston in [The] P[aston] Lett[ers] III. 81 A few Frenchmen be whyrlyng on the coasts, so that there no fishers go out. 1558 [actually 1578?] W. Towrson [The third and last voyage of M. William Towrson to the coast of Guinie, and the Castle de Mina, in the yeere 1577] in Hakluyt Voy[ages] (1589) 125 The Christopher being the headmost & the weathermost man, went roome with the Admirall. 1665 Lond[on] Gaz[ette] No. 3/4 They chased a Barbadoes and a Jamaica man into Limrick.
It thus appears that man as a term for a ship or other vessel comes by simple transference from man in the sense of "human being." Just as in common parlance today a game piece can be a man, so in centuries past could a ship. Simple or not, the application of man to produce compound names for ships doesn't produce entirely predictable patterns of meaning. For example, the "Frenchmen" in John Paston's March 8, 1473, letter are evidently French navy ships sailing under the French flag; but an Indiaman (a word that the OED dates to 1709) is a European ship engaged in trade with India, and a merchantman (dating to 1627) is a trading ship operating in service to one or more private merchants.
To cloud the picture somewhat, I note that a number of fairly early accounts included in the Early English Books Online database allude to ships with men of war onboard. For example, from Richard Grafton, A chronicle at large and meere history of the affayres of Englande and kinges of the same deduced from the Creation of the vvorlde, vnto the first habitation of thys islande (1569):
And in this tyme also the French king had sent diuers Ships vnto the Sea with men of warre for to take the English Marchauntes, and other that came in their course.
From Raphael Holinshed, The firste [laste] volume of the chronicles of England, Scotlande, and Irelande conteyning the description and chronicles of England, from the first inhabiting vnto the conquest (1577):
In the latter ende of this eleuenth yeare was the Erle of Arundell sent to the sea with a greate nauie of ships and men of war.
And from Thomas Chuchyard, A generall rehearsall of warres, called Churchyardes choise wherein is fiue hundred seuerall seruices of land and sea as seiges, battailes, skirmiches, and encounters (1579):
The Turkes vppon the arriuall of the Christians, plucked backe their Batterie, and embarked their greate Ordinaunce, and retired their men of warre a Shipborde, but in their retire thei loste fifteene hundred Turkes, and those soldiours that were before penned vp issued out, and recouered twoo greate Cannons, Dom Garsia was gone backe again to Saragosa, for the residue of the Armie.
In these instances, the "men of war" are soldiers, marines, or other fighting men on board ships—so you might argue that "man of war" in the sense of "vessel equipped for warfare" originally arose in the context of instances where a ship was, in fact, loaded to the gills with human "men of war." The OED, however, does not seem to view this origin story as necessary or likely to explain the more general use of man as equivalent in meaning to ship.
