Word experts say this comes from a children's book called "The History of Little Goody Two-Shoes," which was popular in the 1760s. In that era in England, Goody was short for Goodwife, a courtesy title used almost like "Mrs." The book's main character was so poor she had only one shoe. She was thrilled to get a matching pair and earned the nickname in the book's title, which basically meant "Little Mrs. Two Shoes."
Goody Two-Shoes is now used to indicate someone who's angelic or self-righteous, apparently out of a misunderstanding of the original usage of goody.