1610s, from shoe (n.) + string (n.). As figurative for "a small amount" it is recorded from 1882; as a type of necktie, from 1903; as a style of cooked potatoes from 1906.
shoehorn
shoelace
shoeless
shoemaker
shoe-shine
shoe-string
shofar
shogun
shogunate
shoo
shoo-fly