All three words describe being without shoes, but they differ in scope and register. Barefoot is the most common everyday word, used for people casually walking or standing without shoes. Shoeless is less frequent and often implies a temporary state — for example, guests asked to remove shoes indoors. Unshod is the most formal or technical of the three; it also applies to horses without horseshoes, a meaning the other two words do not carry. You would say 'the children ran barefoot on the grass' or 'the hotel asked guests to remain shoeless by the pool,' but only unshod describes a horse on a rocky trail.
Unshod combines the Old English prefix un- ('not') with shod, the past participle of shoe. The word has been used since the 1500s to describe both barefoot people and horses without metal shoes.