Early discussions of the phrase 'neck of the woods' in reference works
Maximilian Schele De Vere, Americanisms; The English of the New World (1872) believes that the phrase "neck of the woods" was not only native to the United States but especially common in the nation's Southwest (a designation that, at the time referred primarily to the region occupied by Texas, Arkansas, and Louisiana):
If the settler find no home on an island or in a cove of a prairie, he prefers, especially if he be German, a Knob, as from its resemblance to a knob (Germ. Knopf), any rising is called in the West. ... Should he build his cabin in a forest, he will soon find his neighborhood designated as a neck of the woods, that being the name applied to any settlement made in the well-wooded parts of the Southwest especially. Should he dread the bush, he may choose one of those beautiful forest glades called oak openings and found in the Northwest.
An assessment of the phrase similar to De Vere's appears in John Bartlett, Dictionary of Americanisms: A Glossary of Words and Phrases, Usually Regarded as Peculiar to the United States, second edition (1859):
NECK OF THE WOODS. In the wooded sections of the South-West this term is used in speaking of any settlement, place, or plantation.
[Example:] I am the only subscriber to the Spirit of the Times in this neck of woods, and consequently my paper is in great requisition.—Letter from Arkansas, N.Y. Spirit of the Times.
[Example:] It's no use talkin' about your Polar bar and your grizzly bar. They ain't no whar, for the big black customer [the black bear] down in our neck o' the woods beats 'em all hollow.—Traits of American Humor, Vol. II
The phrase "neck of the woods" does not appear in the first edition (1848) of Bartlett’s Dictionary of Americanisms, however.
John Farmer, Americanisms—Old and New (1889) offers this definition:
NECK OF THE WOODS. — A plantation or settlement situated in woodland districts. This term is mostly met with in the Southwest.
Farmer also observes that the word neck "Generally applied, in old colony days, to land lying between rivers."
"The Dialect of Southeastern Missouri," in Dialect Notes, volume 2, part 5 (1903) has this brief entry for "neck of woods":
neck of woods, n. phr. Neighborhood. 'He doesn't live in this neck of woods.'
Nineteen years later, "Metaphor and Simile in American Folk-Speech," in Dialect Notes, volume 5, part 5 (1922) has this entry:
neck of the woods, n. phr. Neighborhood. "Nobody lives in that neck of the woods." Indiana, Arkansas, Alabama, Nebraska.
That nineteenth-century speakers and writers of British English did not use "neck of the woods" in the sense of settlement or neighborhood is clear from Philological Society, A New English Dictionary on Historical Principles, volume 6 (1908), whose only citation of that sense of the phrase is from De Vere’s 1872 book on Americanisms.
Gilbert Tucker, American English (1921), who handles the phrase very briefly in a chapter of his book called "Some Real Americanisms," makes clear that by 1920 use of "neck of the woods" didn't require the presence of any significant number of trees:
NECK OF THE WOODS—Place, not implying proximity of forest, 1851.
Early newspaper appearances of the phrase
A search of the Library of Congress's Chronicling America newspaper database for the years 1836 through 1845 turns up just two relevant matches for that ten-year period (the database goes back only to 1836). One is an advertisement that ran regularly in the Cadiz [Ohio] Sentinel between March 26 and October 8, 1845, under the eye-catching headline, "Awful Calamity!":
E. C. Stewart, very thankful for past favors, would most respectfully inform his friends and the public generally, that he continues to carry on the Chair Making Business, at the south end of Marker Street, where he has, and intends keeping constantly on hand, a general assortment of FANCY AND WINDSOR CHAIRS, of the latest fashions, made and finished in a style not to be surpassed by any thing that can be scared up in this neck of woods ; and he feels confident, from his long experience in the business, and a desire to please, that he will render general satisfaction to all those who favor him with a call.
And from the Ohio Piketonian (1845) quoted in the [Indianapolis] Indiana State Sentinel on November 29 and December 4, 1845:
INDIANA SENTINEL.—Among all exchanges which come to our table; there is no more welcome visitor than Chapman’s State Sentinel. The paper is right, politically ; and there is a life and vivacity about its editorials which render it both amusing and instructive. Besides all this, its publishers are the 'right sort of stock,'—first rate clever fellows. If any one in this 'neck of woods' desires to know the 'doings' of the Hoosier Legislature, just let them send for the Indiana State Sentinel.—Ohio Piketonian.
Both of these instances are from Ohio, which has never been identified as a “South-Western” state. In the period from 1846 through 1850, the Library of Congress database suggests that the Ohio connection to the phrase remains strong. For instance, from the [Carrollton, Ohio] Caroll Free Press (October 16, 1846), this item:
MAMMOTH BEET.---Mr. Daniel Vanhorn, of Lee township, a few days since, presented us with a beet weighing 12½ pounds. If any other place, in "this neck o' woods," can beat Lee in the beat like, we should like to know it.
Lee, Ohio, is about 7 miles southeast of Carrollton, though both are in Carroll County. That a Carrollton newspaper would view Lee as being "in this neck o' woods"—that is, in the same neck of the woods as Carrollton—suggests that a "neck of woods" in 1840s Ohio parlance comprehended a significantly larger geographical area than many people now think of it as describing.
Other instances of "neck of woods" appear in the [Upper Sandusky, Ohio] Democratic Pioneer on October 22, 1847 (about a bank closure in Yazoo City, Mississippi), on November 5, 1847 (quoting from the Ohio Patriot), and on August 11, 1848; and in the [Ravenna, Ohio] Portage Sentinel on March 17, 1847 (quoting the Steubenville [Ohio] Union), on November 4, 1850, and on December 30, 1850.
The Indiana State Sentinel continued to use the term "neck of woods" too—in a July 11, 1846 in a letter from a reader in Union County Indiana and in a May 20, 1847 report from the Whig convention to nominate a candidate for the nearest Congressional district.
The black bear story that Bartlett cites in 1859, originated in the "New Orleans Delta" (specifically, Yazoo, Mississippi) according to a version of the story that appears in the Wilmington [North Carolina] Journal (January 18, 1850), although the story twice uses the phrase "neck o' woods," instead of "neck o' the woods" as Bartlett’s source does.
Another widely reprinted tall tale—this one about a "bar hunting" adventure in 1843 in Hot Springs, Arkansas—uses the phrase "neck of the woods." This story appears, for example, in the [Stroudsburg, Pennsylvania] Jeffersonian Republican (July 2, 1846):
But, however, I slung 'old Bellzy' over my shoulders, and sat out in full chase after the only bar that we had heard of in that neck of the woods during the summer.
The same story appears in the Ottawa [Illinois] Free Trader (March 20, 1846), the [Abbeville, South Carolina] Banner (June 3, 1846) and in the Baton Rouge [Louisiana] Gazette (April 18, 1846).
Other instances of "neck of the woods" appear in the Jeffersonian Republican (June 1, 1848) and in the [New Orleans, Louisiana] Daily Crescent (March 5, 1850).
Other instances of "“neck of woods" appear in the Sunbury [Pennsylvania] American (August 25, 1849) and in the Wilmington [North Carolina] Journal (January 23, 1846).
Conclusions
The reference works from the 1800s agree that "neck of the woods" originated in the Southwest part of the United States, which in the middle of the nineteenth century was generally understood to refer to the pro-slavery states west of the Mississippi that eventually seceded from the Union in the 1860s: Arkansas, Louisiana, and Texas. Nevertheless, only two of the twenty occurrences of the phrase "neck of the woods" [or "neck of woods"] that appear in U.S. newspapers in the Library of Congress database published in the years 1845 through 1850 are from the U.S. Southwest—in New Orleans and Baton Rouge, Louisiana.
Perhaps that anomaly is attributable to the absence of printing presses in much of the Southwest at this period—and stories printed outside the region that retell "bar hunt" stories from Arkansas and the Mississippi River Delta and a bank failure story from a city on the edge of the Mississippi River suggest that the phrase was indeed popular there.
But the fact remains that the band of Midwestern states ranging eastward from Illinois in the west through Indiana, Ohio, and Pennsylvania accounts for fifteen of the twenty matches from this period. The only exceptions are the two instances from Louisiana, two from a single newspaper in Wilmington, North Carolina, and one from South Carolina. On the strength of this record, I think we must credit the Midwestern states with early (though perhaps not first) adoption of the phrase.
With regard to the distribution of instances of "neck of woods" versus "neck of the woods," Indiana and Ohio sources strongly favor the former, while the Louisiana and Carolina sources use the latter.
As for the original sense of the idiom, the most interesting comment in the nineteenth-century sources may be Farmer’s observation that the "neck" was "in old colony days" defined as land lying between two rivers. By the 1840s, however, it had come to mean simply area or neighborhood. The remaining question is, How large an area was implied by the term? My impression from Carroll County, Ohio, example cited above—in which a town 7 miles away from Carrollton appears to be viewed as falling within the same "neck of woods"—is that it could cover a surprisingly large area.
UPDATE (10/18/2017):
I conducted an Elephind search for "neck of the woods" and it turned up an earlier instance of the phrase than any I had previously found, from "The Marshall University—The Athens of Texas," in the [Clarksville, Texas] Northern Standard (April 17, 1844):
Has every body read the University article, in the last Harrison Times? If not we advise them to go at it immediately.
Our neighbor, excited by the sublimity of the change which has taken place in his neck of the woods within the last few years runs away with himself upon a race madder than that of Phæton with the chariot of the Sun, and fairly revels in the field of fancy.
This instance offers at least some vindication to nineteenth-century lexicographers who identified the expression as an idiom originally from the U.S. Southwest. However, an Elephind search for "neck of woods" (without the definite article before woods) yields an instance from Indiana almost six years earlier. From a letter to the editor submitted by "Ocof Ocol" (that is, "locofoco" backward) and published in the Richmond [Indiana] Palladium (July 28, 1838):
There are one great difference between us gentlemen loafers and the "Eastern gentlemen—the "ruffled shirt gentry"—they wear ruffles on their bosoms, and we on the neither end of our shirts, as all modest men would do. I were born in these "neck of woods" and I'm not to be sceered into measures. I'm one of the vigilance committee of holy democracy, and I knows what's what. I'm for democracy and Nullification! at least that's what our big office-holder told me Ize for.
So the prize for earliest confirmed instance of "neck of woods," now going back to 1838, remains firmly in the grasp of the U.S. Midwest, at least for now.