Generally, if taking data from a database, I'd say to get all the date formats sorted out at DB level before they get passed to Perl. MySQL, for instance, has date_format() which means that the date can come straight out of the query without further need of manipulation.

However, for the abhorrent date format used by the HTTP protocol (required for HTTP headers including expiries, cookies, etc), I would second (or third) the use of HTTP::Date. This module and Date::Calc form the best part of my Perl date-manipulation toolkit.