[Update 9/16/16: The test below was run on a 100Mbps Ethernet connection (an older building with old Ethernet wiring). Be aware that if you have 1Gbps or more on your LAN all the way from the client to the server, you will take more time using high compression methods as the network connection basically waits around for the CPU to crunch data. In that case just go with -z1p. Using NO compression seems to not provide any real speed advantage over -z1p, at least on modern systems.]
Description of tested compression methods from Clonezilla:
-z1p, --smp-gzip-compress Compress using parallel gzip program (pigz) when saving: fast and small image file, good for multi-core or multi-CPU machine
-z2p, --smp-bzip2-compress Compress using parallel bzip2 program (pbzip2) when saving: faster and smallest image file, good for multi-core or multi-CPU machine
-z3, --lzo-compress Compress using lzop when saving: similar to the size by gzip, but faster than gzip.
-z5p, --smp-xz-compress Compress using parallel xz when saving: slow but smallest image file, faster decompression than bzip2.
Computer: 13in MacBook Pro Mid-2012 / Core i5 2.5Ghz / 4GB RAM / 500GB HDD (5400RPM) / OSX Yosemite
Partition: HFS Plus / 22.9GB used of 498.9GB
Network: SMB NAS share (WD My Cloud EX2) over 100Mbps Ethernet LAN
Clonezilla Live USB [clonezilla-live-20150805-vivid-amd64.iso converted to .img and written out to USB (dd)]
No image encryption
Using final time for partition as reported by Partclone
Time to Save Partition and Compressed Size:
-z1p: 25:38 - 16.5GB BEST
-z2p: 26:36 - 16.1GB +0:58
-z3: 27:08 - 17.5GB +1:30
-z5p: 33:10 - 15.0GB +7:32
Time to Restore Partition:
-z1p: 26:35 +3:34
-z2p: 24:46 +1:45
-z3: 28:22 +5:21
-z5p: 23:01 BEST
-z1p: 52:13 +0:51
-z2p: 51:22 BEST
-z3: 55:30 +4:08
-z5p: 56:11 +4:49
-z2p, or parallel bzip2, is the all around winner. Parallel xz (-z5p) restores very fast but it's backup time is very long, so it seems to be best suited for images that will be used often to restore lots of machines. The other options tested don't show any particular strengths.
So which to use?
Consider an image that gets updated quarterly and restored 24 times in one year. Total Clonezilla times would be:
-z1p: 740.53 minutes
-z2p: 700.80 minutes
-z3: 789.33 minutes
-z5p: 685.07 minutes
So then it makes more sense to use -z5p in that scenario. However, -z2p has the edge if you change that scenario to using the image only 15 times per year. -z2p also is better is you change the scenario for 7 updates per year and 24 uses. But I've never updated images more than 4 times a year without a good reason. So if you are going to use an image a whole lot, -z5p is the way to go. For occasional use or if you plan to update the image on a frequent basis, -z2p is better.