Metals, as well as some organic compounds, are very persistent in soil and will not "go away" at all (metals) or only minimally over time (persistent organic chemicals). So what should you test for?
Lead is ubiquitous in most soils, especially in urban areas, because of the use of leaded gasoline. In addition, the use of lead based paint contributes lead to soils on formerly residential lots as did the historic practice of changing the oil in your car or mower and not properly disposing of it. Lead levels of 200-300 mg/kg in urban soils are common.
If you want to establish a garden in an area with naturally occurring elevated levels of arsenic in the soil (for example in Indiana, eastern Kansas, Iowa, etc.), you may want to find out exactly how much arsenic is in your garden soil. Your State Geologic Survey office will have general information as to how much arsenic to expect on average.
Contaminants from historic site use
Collecting soil samples for environmental samples can be a bit tricky as certain handling procedures and sample containers may be necessary.
Testing Your Soil for Contaminants (pdf) provides guidance on where to sample, how to sample, and a list of resources for analyses of lead, other metals and arsenic, aside from commercial laboratories.