"one who acts in place of another," early 15c., from Old French substitut (noun use) and directly from Latin substitutus, past participle of substituere "put in place of another" (see substitution). Military draft sense is from 1777, American English. Team sports sense is from 1849. Of foodstuffs, from 1879. As an adjective from early 15c.
"submarine boat," 1899, from submarine (adj.), perhaps short for earlier submarine vessel (1732), etc. Earlier "a creature living under the sea" (1703). The short form sub is attested from 1917. As a type of sandwich from 1955, so called from the shape of the roll. Related: Submariner.