If I recall correctly (and it's been a few years since my oceanography seminar), it has to do with the ratio of component elements in the shells of benthic fauna. They're pulling those elements in as a part of the growth of those structures, and the ratio of different gases changes based on the temperature.

EDIT: Looked it up, I had the gist of it I guess. http://en.wikipedia.org/wiki/Paleothermometer#Mg.2FCa_and_Sr...

I imagine the techniques now are more refined than what is exactly mentioned there.

Semi-related, I got to take sediment cores from a Ramsar wetland while in South Africa in order to pick them apart for pollen to try and indirectly measure early-Holocene temperatures using the ecology as a proxy. Interesting stuff, and fun to be in the field.