Long discussion here, but essentially just a gathering of competing speculations. Earliest citation is said to be in the 1950's but the earliest quoted I have seen is 1962.

Wikipedia says "While no written occurrences with the modern meaning have yet been found predating 1962, a number of anecdotal recollections suggest the phrase dates back to sometime in the 1950s, potentially into the 1940s. One of the better-documented cases is provided by Captain Richard Stratton, who recorded in 2005 that he encountered the phrase during naval flight training in Florida in July 1955 as part of a ribald story about a mythical Scotsman.".

Another site gives this example from 1962:

The current holder of the "earliest attestation" crown was found just last week by Stephen Goranson, who announced his discovery on the American Dialect Society mailing list (ADS-L). It shows up in "Man on the Thresh-Hold," a rambling short story by Robert E. Wegner in the Fall 1962 issue of Michigan's Voices, a quarterly literary magazine. Here is the long stream-of-consciousness sentence in which it appears:
(text of example is a bit map. See original here. ...)

Who knows why a "brush salesman" would be fond of saying "the whole damn nine yards"? This was the era of the Fuller Brush man, the legendary traveling salesman who would go door to door hawking brushes, brooms, mops, and so forth. Maybe it took nine yards of material to make a mop!

Short answer: provenance not known.