There are a couple theories, both somewhat intertwined, on the origins of "Podunk" meaning an insignificant, backwater town. In Algonquian "podunk" or "pautunke" means literally "where you sink in mire" and was given to various areas along rivers. This explains why there are a number of small towns in the North East all called "Podunk".

"Say there nice Indian fellow who we're about to nearly exterminate when we invent the Winchester rifle and smallpox infected blankets, would you be a good chap and tell me what this place is?"

"Podunk."

"Thanks! I hereby declare this to be the town of Podunk and you are the first to have the honor of paying property tax. Be aware, as of this minute you are in arrears."

These are the literal Podunk towns of the USA:
There used to be a Podunk, Wisconsin but that was abandoned long ago.

Since building your town in the middle of a swamp basically ensures limited growth because people simply don't want to emigrate to a swamp (unless you can offer them jobs in advertising), it's no wonder "Podunk" has long been associated with insignificance, isolation, an inability to keep up with the times, and a citizenry not overly blessed by shrewd judgment (i.e., "Dudes, don't live in a marsh!").

The first known use of podunk to refer to a backwater town was a letter to the editor of the Buffalo Daily National Pilot. In 1846, a letter writer spoke of a mythical, isolated town called Podunk that was "a little world of itself." This actually started the notion in the popular press that there existed no such town called Podunk in the USA. In 1933 the Boston Herald alleged "Podunk, like Atlantis, has no locus." A reader challenged the Herald's assertion, noting he swore there was a Podunk near Worcester, Massachusetts.

The Herald mounted an expedition to find this mythical Podunk. Found it, they did. The first found Podunk was an unincorporated community 15 miles west of Worcester.

It's interesting to note that the first recorded encounter between Europeans and Indians was with a subset of the Algonquins called the Podunk tribe. In the early 1600s, Dutch navigator Adrian Block piloted the Quinnehtukqut River. The first place he landed was just north of Hartford, at a Podunk village!