One of the best records we have of what carbon dioxide levels have existed in the atmosphere is from ice core samples. Ice is taken with specialized instruments, usually from East Antarctica. Due to differences in the way air bubbles freeze (they will be opened up if they are near the edge of a layer), the amounts of gasses in the closed bubbles near this can be identified, collected, and measured. In the first article I attached (from 1998), the data the scientists have goes back through four climate cycles and 420,000 years. The details of this process are in the article ("kyr" in the article means thousands of years).
The second, more recent article from 2012, has analysis of a core measuring 800,000 meters.
The third article discusses another method of estimating carbon dioxide levels, by using plant fossils. The CO2 levels of plants in sedimentary rock has been found to be a good indicator of atmospheric CO2 levels.