For MacOS X, you could try the following approach:

• Make an application directory (e.g. image2swf.app) and a subdirectory lib for all the libraries.
• Install the necessary libraries (e.g. ImageMagick) inside that directory, using e.g.

  configure --prefix=/my/path/image2swf.app/lib
  make
  make install
  [download]

• Do the same for all modules:

  perl Makefile.PL PREFIX=/my/path/image2swf.app/lib
  make
  make install
  [download]

• Put your script in there (for exact location, see below)
• Modify your script to use your library directory:

  use lib qw(lib)
  [download]

• Put all the other necessary files (resources, icon etc.)

I don't have an article handy that shows the structure of Mac OS X app-directories, but you might google for it or look at another app to see how it's done. The created app will look to the user as one file.

Update: I'm not recommending this for linux because distributing compiled versions of software (ImageMagick in that case) can be problematic on linux (library issues, different kinds of processor (x86, Sparc), etc.)