When I was exploring my ideas about Speeding up point-in-polygon -- take two I needed some sample data and I cast around and found this US government site that has zip files (sic) containing polygons for all the US 5-digit zip codes, by state.

They are in a complex format, .e00, but there is a Geo::E00 for reading them. The polygons are defined in terms of longitude and latitude with appropriate corrections etc. Although you don't need the polygons per se, each polygon represents a single zip code and each also has a centroid which you could extract (the module has a method for doing this directly), and use it to represent the entire zipcode.

Should be reasonably accurate data given the source, and best of all, it's legitimately free.

Just a word of caution I came across when looking before Zip_Codes_are_Not_Areas.