They use something called "climate proxies". Because temperature influences the types and rate of growth in living things, one can make some assumptions about temperature regimes in the past. So, coral growth, tree rings, pollen types, diatomaceous material in ocean sediments and the like all provide clues to what the temperature was like in the long past. I don't know how defined these values are (i.e., uncertainty around the temperature values) but it definitely is indicatory and helps us understand the relationship between GHGs and temperature change.
For more information, try the Real Climate website where real climate scientists answer questions about global warming.
To answer this question I would need to see the reference that shows that global temperatures were at a million-year high, because I am not familiar with the assertion in the scientific literature. I am aware of 2000-year reconstructions of global temperature by Michael Mann et al (perhaps the questioner means millennial instead of million-year?). These reconstructions are discussed well in many entries on the Real Climate website or on Wikipedia.
These reconstructions of the past 2000 years rely on the data available from tree rings, corals, and ice cores. The statistical methods are complicated, but part of the effort was to conduct an error analysis of the reconstruction, and it shows that the temperatures since 1998 are statistically higher than those in the last 2000 years.
As John aptly puts it, there are indicators in ice cores, now extending back 740,000 years in Antarctica. The isotopic compositions of hydrogen - and to a certain extent oxygen - in the ice can reflect changes in the temperature of precipitation over the ice core sites. These records over Antarctica in fact show that in the older part of the record before 430,000 years ago, the temperature departures during warm periods were less intense than those we see today in that last 430,000 years. Although Antarctica serves as our best record of long-term climate change over the last 800,000 years, I always caution people to remember that Antarctica represents one point on the globe.
If one wishes to move further back in time, there are geologic records that have been produced from marine sediments, and many of these extend back as far as 65 million years. Although there are other proxies, many records measure the chemical composition of fossilized foraminifera - single-celled animals that live in the ocean and form a calcite shell that inadvertently records the characteristics of the water around it. As you might imagine, reconstructions of deep ocean water characteristics provide a fascinating record of how climate has varied in the past, but they are a bit removed from the historical record of the atmosphere of the last century, and it would be a challenge to compare them in the same way we do with Antarctic ice cores or tree rings.