Different md5sums for same tar contents

As Dennis pointed out above, it's gzip. Part of the gzip header is a mod time for whatever is compressed in the file. If you need gzip, you can compress the tarfile as an extra step outside of tar rather than using tar's internal gzip. The gzip command has a flag to suppress the saving of that modification time.

tar -c ./bin |gzip -n >one.tgz
tar -c ./bin |gzip -n >two.tgz
md5sum one.tgz two.tgz

This will not affect times inside the tarfile, only the one in the gzip header.

To make a tar file with a consistent checksum, just prepend GZIP=-n like this:

GZIP=-n tar -zcf myOutputTarball.tar /home/luke/directoryIWantToZip

How this works: Tar can accept gzip options using a temporary GZIP environment variable, as above. Like Valter said, tar uses gzip, which by default puts a timestamp in the archive. This means you get a different checksum when you compress the same files. The -n option disables that timestamp.