c. 1300, "narrow band or strip of cloth" (oldest use is as a technical term in heraldry), from Old French label, lambel, labeau "ribbon, fringe worn on clothes" (13c., Modern French lambeau "strip, rag, shred, tatter"). This is perhaps, with a diminutive suffix, from Frankish *labba or some other Germanic source (such as Old High German lappa "flap"), from Proto-Germanic *lapp-, forming words for loose cloth, etc. (see lap (n.1)).
Meanings "dangling strip of cloth or ribbon used as an ornament in dress," also "strip attached to a document to hold a seal" both are from early 15c. General meaning "tag, sticker, slip of paper" affixed to something to indicate its nature, contents, destination, etc. is from 1670s. Hence "circular piece of paper in the center of a gramophone record," containing information about the recorded music (1907), which led to the meaning "a recording company" (1947).