The construction you describe in which the do auxiliary is used, among other things, to form questions is called do periphrasis, and the usage of the do auxiliary in this way is termed periphrastic. Also note that it is not restricted to simple past: compare your example "Where did you go last night?" (past) with "what do you mean?" (present).
Many linguists 4 have been studying the origin of this phenomenon because it sets English aside in the Germanic family of languages. And whilst many different explanations have been offered during the past 50 years, the one which is currently gaining acceptance is that of a Celtic influence (more specifically Cornish).
A recent convert to the so called "Celtic Hypothesis (CH)" is no less than John McWhorter of "Our Magnificent Bastard Tongue" fame who in a recent (2008) paper revisits his previous (2002) explanation of a Viking influence and debunks a number of objections upheld by the CH opponents (recommended reading accessible to non specialists).
In fact, this construction is completely absent of Old English which closely follows the Germanic syntax1.
Regarding the Celtic influence, let me quote McWhorter:
one would be hard pressed to name a language one
had learned or was even aware of that used do in this particular way. That is, unless one is a
speaker of, or familiar with, a Celtic language, in which case one is confronted with a close
parallel.
The late Alvar Ellegård, a Swedish professor of English at the university of Gothenburg has plotted this graph of the appearance of the periphrastic do in Modern English2.

My understanding of the chain of events is as follows.
- Following the influx of Vikings in the Danelaw, Old English looses its complex inflections system inherited from its Proto Germanic origins. There is plenty of evidence for this.
- In the process, English evolves from a synthetic language to an analytic language3.
- There is therefore plenty of room for the pervasion of some brittonicisms (among which do-periphrasis) into Middle English, which had till then been barred from entering English.
Also have a look at the famous Middle English creolisation hypothesis.
Note 1
Examples of Old English interrogative form. The verb and subject are simply inverted compared to the indicative mood.
- Canst þu ænig þing? - Kannst du einige Dinge (German) - Can you do any thing?
- Hwelcne cræft canst þu? - Welche Kraft kanst du? (G.) - What craft can you?
- Hwæs hunta eart þu? - Was für ein Jäger bist du? (G.) - What hunter are you?
Note 2
Alvar Ellegård was not a proponent of the Celtic Hypothesis. He worked on the subject in 1953 and this theory was only nascent at the time.
Note 3
Roughly speaking, a synthetic language relies on inflections to avoid ambiguity whereas an analytic language relies on word order to avoid ambiguities.
Note 4
Dal (1952), G.Visser (1955), Preusler (1956), Poussa (1990), Klemola (1996, 2000), Tristram (1999), Filppula (2003), Hickey (1995), Vennemann (2000, 2001), Van der Auwera & Genee (2002), White (2002), Poppe (2003). The contributions of Hamp (1975) and even J.R.R. Tolkein (1963) have also been useful.