"showy, tastelessly rich," c. 1600; earlier "joyfully festive" (1580s), probably a re-adjectivizing of gaudy (n.) "large, ornamental bead in a rosary" (early 14c.) via the noun gaud + -y (2.). In early Modern English it also could mean "full of trickery" (1520s).
Or possibly the adjective is from or influenced by Middle English noun gaudegrene (early 14c.), name of a yellowish-green color or pigment, originally of dye obtained from the weld plant (see weld (n.1)). This Germanic plant-name became gaude in Old French, and thus the Middle English word. Under this theory, the sense shifted from "weld-dye" to "bright ornamentation."
As a noun, "feast, festival" 1650s, from gaudy day "day of rejoicing" (1560s).