Lots of web sites offer this data (see http://www.google.com/search?hl=en&q="average+temperature"+by+zip+code) but I don't see the dataset they are using.
I looked at the national weather service for a bit (see for example http://www.rdc.noaa.gov/~foia/index.html#electronic), and didn't see it. NWS is in the National Oceanic and Atmospheric Administration (NOAA). NOAA links:
- http://www.ncdc.noaa.gov/oa/climate/climatedata.html#monthly
- http://www.ncdc.noaa.gov/oa/climate/research/cag3/explain.html.
It looks so close, but I still haven't found it.