Is it really true that you should compress before you encrypt? IT seems to me that the encrypted message should have the same amount of "information entropy" as the original message, so it should compress equally well.
Definitely compress first. While it is true that there is the same amount of entropy before and after encryption, you'll never be able to identify it from the bitstream (otherwise your encryption is broken). Compression works by understanding statistical patterns in the process that is creating the data stream, and encoding the data based on this information to achieve a reduced stream size. An encrypted stream is generally assumed to be indistinguishable from random data, so you won't get nearly as much (if any) compression from this pseudorandom stream.
I always thought it was good to compress first because you can more easily avoid frequency attacks. In that way I think it's better to compress then encrypt.
EDIT: That and you get to encrypt a shorter data stream. I realize frequency attacks aren't as much of a concern these days but it's just the first thing that came to my mind.
Also, some encryption systems integrate compression; like OpenPGP -- it supports ZIP, ZLIB, and BZIP2. So in such case, it may well be just sufficient to encrypt uncompressed data.