Perhaps it will be sufficient to provide them with a copy of your cygwin1.dll, at least this worked for me in a similiar case. (If they already have cygwin on their machine, the program wouldn't complain about missing it)

However, probably the cygwin1.dll must be suited for their system (XP/7/8, 32 vs. 64 bit, whatever) - and be compatible to your version of cygwin...

If, however, you want to distribute only one (executable) file, you have to go with one of the "native" ports, like ActiveState, Strawberry, Citrus, DWIM or so, as proposed in Re: Using pp (Perl Packer) with cygwin (don't). I think it should be possible to install (and use) it alongside with your cygwin perl...

Update: you might find this: Newb guidance for Perl on MS Windows: Cygwin, Strawberry, ActivePerl? informative (despite the "newb" in its subject)