I think Geo::PostalCode would be at least a look. It reads the zipcode/city data from Bearkly DB's that you can get from http://www.census.gov/geo/www/tiger/zip1999.html.
It seems pretty stright forwards, the relivant section from the docs is below:
$gp = Geo::PostalCode->new(db_dir => $db_dir);
Returns a new Geo::PostalCode object using the postalcode.db, latlon.db, and city.db Berkeley Database files in $db_dir.
$record = $gp->lookup_postal_code(postal_code => $postal_code);
Returns a hash reference containing four keys:
* lat - Latitude
* lon - Longitude
* city - City
* state - State two-letter abbreviation.
Hope that's of some use to you. . .