Wordorigins.org

This Americanism, meaning mediocre or of moderate quality, dates to at least 1837. From A Succinct Account of the Sandwich Islands in the Southern Literary Messenger of July 1837:

A Dinner on the Plains, Tuesday, September 20th.—This was given “at the country seat” of J.C. Jones, Esq. to the officers of the Peacock and Enterprise. The viands were “from fair to middling, we wish we could say more.”

It probably comes from a system for rating the quality of cotton, although it isn’t recorded in the cotton sense until well after its appearance in a general sense. From the 1889 Century Dictionary:

Fair to middling, in com., like fair, 8, moderately good: a term designating a specific grade of quality in the market.

Somewhat earlier, we can find references to the use of fair and middling to cotton, but not the specific form fair to middling. From J.T. Trowbridge’s A Picture of The Desolated States from 1868:

The quality of Middle Tennessee cotton never rates above "low middling," but generally below it, (the different qualities of cotton being classed as follows: inferior, ordinary, good ordinary, low middling, middling, good middling, middling fair, good fair, and fine.)

So the question is whether or not the specific sense meaning cotton came first and then generalized or whether the general sense came first and then specialized in some circles to refer to a specific grade of cotton. The evidence would point to the latter, but we cannot absolutely rule our the former.

(Sources: Quinion’s World Wide Words; ADS-L; Oxford English Dictionary, 2nd and 3rd Editions)