Depends, how clueless is the target audience?

I would say I could assume they have basic Linux knowledge and can run scripts and answer interactive questions if needed in these scripts.

How dependent is your software on non-standard libraries (unlike expat,libxml2,libgd...)?

Not sure what you meant by non-standard libraries, every CPAN dependency I have is non-XS or has a non-XS version.

Does your software require specific versions of cpan modules?

No, works with any recent versions of libraries.

See this presentation and the mentioned solutions Seen in PerlWeekly newsletter: Carton CPAN dependency manager, maybe you use par, or cpan2rpm/cpan2deb...

Thanks for the heads up on Carton, didn't know this existed and I see T. Miyagawa recently started the project, this is great.