photograph: David Levene for the Guardian
In the sense of a person one chooses to socialise or associate with, this noun dates back to the early 14th century. It is from Anglo-Norman and Old and Middle French forms such as compaignun and compaignon (Modern French compagnon), derived from Late Latin companio/companion-, attested around 800 in the plural companiones in the Lex Salica (the Salic law, i.e. the code of the Salian Franks).
Based on the classical Latin prefix com- (with) and noun panis (bread) and literally meaning one who breaks bread with another, this Late Latin noun was probably a calque of an unattested Germanic compound formed similarly to Gothic gahlaiba, composed of the prefix ga- (with) and hlaib (loaf). Both the Latin and Germanic nouns had the sense of messmate, person with whom one habitually eats meals.
From Latin companion-, compaignun, compaignon, etc., were originally the objective case forms, while the subjective case forms were cumpaing, compain, etc., (Modern French copain), from Latin companio.
(The objective case is a case of nouns and pronouns serving as the object of a transitive verb or a preposition. The subjective case is a case of nouns and pronouns used for the subject of a verb.)
The feminine of French compagnon is compagne and that of copain is copine. The latter pair of words is used in the familiar language register to mean friend but also boyfriend/girlfriend in the romantic or sexual sense.
The obsolete English noun companage meant food eaten as an accompaniment to bread, especially as part of an allowance to a worker, tenant, etc. Via Anglo-Norman and Middle French compenage, companaige, companage, etc., it is from Late Latin companaticum, based, like companion, on the classical Latin prefix com- and noun panis.
The nautical term companion appeared in the early 18th century in the sense of a raised frame with windows on the quarterdeck of a ship to allow light into the decks below. With folk-etymological alteration after companion in the sense of partner, this noun is probably from the obsolete Dutch noun kompanje (later kampanje), meaning elevated structure at the rear of a ship.
This Dutch noun is itself probably, via French compagne, from the obsolete Italian (camera della) compagna, (storeroom for) provisions, from Late Latin compaigna, compagna, provisions, perhaps ultimately based on the classical Latin prefix com- and noun panis. But there may also have been confusion with Late Latin capanna (the origin of the noun cabin), and in fact, some regard this as the true origin of the nautical term companion.