Which cygwin package do I install to get the
Install gcc, make, autotools etc into cygwin, download the software and compile it yourself (natively, under windows, so you get a windows, native binary) as it doesn't seem to be offered by cygwin.
The README for the software has a section on windows:
= Minimal installation =
If you just need parallel and do not have 'make' installed (maybe the system is old or Microsoft Windows):
wget http://git.savannah.gnu.org/cgit/parallel.git/plain/src/parallel chmod 755 parallel cp parallel sem mv parallel sem dir-in-your-$PATH/bin/