Short Answer / Summary
Many fossils have living relatives of which we know the environmental preferences, such as temperature. By identifying the fossils and combining this data with known preferences, palaeoclimates can be reconstructed.
Non-biting midges as an example
Non-biting midges, also known as chironomids, larvae are a good example of how palaeoclimates can be reconstructed using (sub)fossils. Chironomids occur in almost every freshwater system on Earth and are comprised of many different species. The larvae of these species live in the sediments of lakes or rivers. Some of these species prefer cold water, whereas others prefer warmer waters. Yet other species prefer nutrient-enriched (eutrophied) waters, and so on.
If and when a larva dies, there is a chance that its head capsule is stored within the sediment. These head capsules are well-preserved as they are made of a resistant material, chitin. When researchers retrieve such sediments from lakes (or rivers in rare cases), they can choose to study the material using microscopy to identify certain types of chironomids. These types encompass one or more different species, because the remains can often not be identified to species-level.
Each layer of the sediment reflects a different time period and by identifying the chironomid assemblage present in these layers, we are able to roughly determine which species have lived there. Comparing these assemblages to the environmental preferences of living relatives of these (sub)fossil chironomids then allows us to finally determine what the local climate was like all those years ago.
Each (sub)fossil group (e.g. pollen, chironomids) has its own applications. The chironomids discussed above are, for example, mostly used in reconstructions of (1) temperature, (2) water depth, and (3) eutrophication. It is always important to keep in mind that some species may be sensitive to more than one variable, so the interpretation of data needs to be based on assemblages rather than individual species, or types.
I have added two photos of chironomid subfossils from my own research at the end of this answer with a short explanation of each type to illustrate what I have described above. I will not go into the details of how to identify these head capsules, as that is irrelevant to the question asked.
Source: This answer was written based on my own experiences with research on fossil pollen and chironomids to reconstruct past climate and environments.
Photo #1: Tanytarsus lugens-type
The chironomid species which comprise the type shown above are known to occur in colder lakes, and a high abundance of these head capsules is therefore indicative of colder conditions.
Photo #2: Chironomus anthracinus-type
This type mostly encompasses species which prefer warmer conditions, and as such are more prevalent in warmer time periods.