A really interesting paper appeared in this weeks Nature. (Unfortunately, requires a subscription to access the full paper, but you can get a copy at a local bookstore.) The authors used phylogeny based statistical techniques to reconstruct ancestral proteins for several bacteria. The results independently show (and collaborate other evidence) for paleotemperature trends from as far back as 3.5 billion years.
Phylogeny based ancestral protein sequencing is not fool-proof, but the evidence seems convergent: the seas were considerably warmer billions of years ago (30 degrees Celsius seems likely) during the early development of life.