Check out PDF::Labels
I've been using that with good success in a mapping program at work. You graphically select the properties you want to mail something to, optionally add a buffer and then generate the PDF of labels. One note, in Acrobat Reader you want to uncheck shrink to fit page or anything similar in the print options. This seems to screw up the alignment. When that option is unchecked it seems to work fine on all printers.
It comes with a number of predefined formats the first one matches Avery 5160 and 5260 I think. If you look at the source to the module it'll give you descriptions of each format.
There are also some modules for doing this with PostScript I believe.