In the American South the word done can be inserted into a sentence before a past tense verb. This is, at least, true in Eastern Texas and some of Louisiana. As this is the area where I have lived my whole life, it is the only region I can speak authoritatively about. I have seen hints on the 'net that this weird grammatical eccentricity may be far more widespread, but I can’t say so with any real conviction.
"We done ate the best chicken fried steak the other night."
In this example, the word done acts as a sort of emphasis, a way of reinforcing both the fact that the action took place in the past, and that this action was in some way notable. The word may also indicate that the speaker means business.
"I just about done had it with you!"—Real-life example from a friend’s grandparents.
This sort of oddball grammar may, at times, be a little bit difficult for outsiders to untangle...which could be the point. Such tortured constructions as "We ain't done went to the movies in a long time" come up in conversation at times, which may cause actual pain to persons who are interested in English language grammar.
The past tense character of this word can be used to emphasize that a long time has elapsed since the action in question was performed:
"He done left here hours ago."
It can also be used to emphasize that the action definitely, unquestionably did occur:
"I don’t want to go see the Little Mermaid. I already done seen it."
Of course, as with many eccentric colloquialisms, done may largely be used for effect. Some people seem to feel that such quaint grammatical constructions lend an air of "homey" or "authentic" character to their speech. It may also be played (partially, at least) for laughs (grins, at least), as a sort of old-fashioned, funny way of saying something.
For others, this, and other such quaint regionalisms, sound ridiculous and uneducated. In northeast Texas, there is a strong division between the big city (such as Dallas or even Abilene) and the smaller towns. The bucolic folks mistrust the cities’ crowds, crime, and corruption and the urbane urbanites look down their noses at the rural areas as economically depressed hives of bumpkins and rednecks. The distinctive patois of the rural Texans is probably, at least in part, an attempt to distinguish themselves from the vice and pretentiousness that characterize the bigger cities.
In the city, you won't find too many people who will use done in this fashion. In the country, it seems to be pretty widespread.
Of course, it can also be used for any combination of these motives—but every Texan child knows to dread their parents’ admonition:
"I already done TOLD you..."
References:
I could find no scholarship on this strange construction, either at the library or online, only because I had no idea where to look. Apparently, it is called the completive done, and is well-documented in the scholarship of people who string a lot of familiar words together in unusual ways. (Thanks to kthejoker for pointing that out.)
Because my educational background is insufficient to decypher the language of these guys, all of the information in this article is from 43 years of living in the Lone Star State, and with conversations with several people who live here.