early 13c., "represent in painting or drawing, portray;" early 14c., "paint the surface of, color, stain;" from Old French peintier "to paint," from peint, past participle of peindre "to paint," from Latin pingere "to paint, represent in a picture, stain; embroider, tattoo," from a nasalized form of PIE root *peig- "to cut, mark by incision."
The sense evolution between PIE and Latin was, presumably, "decorate with cut marks" to "decorate" to "decorate with color." Compare Sanskrit pingah "reddish," pesalah "adorned, decorated, lovely;" Old Church Slavonic pegu "variegated;" Greek poikilos "variegated;" Old High German fehjan "to adorn;" Old Church Slavonic pisati, Lithuanian piešiu, piešti "to write." Probably also representing the "cutting" branch of the family is Old English feol (see file (n.2)).
To paint the town (red) "go on a spree" first recorded 1884; to paint (someone or something) black "represent it as wicked or evil" is from 1590s. Adjective paint-by-numbers "simple" is attested by 1970; the art-for-beginners kits themselves date to c. 1953.