I tend to go with a variant of thezip's method, but I flow the results of the localtime slice through a coderef to make the month and years readable to an ordinary human. So it goes something like this:

my $fn = sub {
        sprintf
            "$base_name-%04d-%02d-%02d-%02d%02d%02d.ext",
            $_[5] + 1900, $_[4]+1, reverse(@_[0..3])
    }->(localtime);
[download]

Like thezip, I use a YYYY-MM-DD format so that files sort nicely in a directory.