How can I recursively bzip2 all files that aren't bzipped?

find is your friend. I reckon the following ought to do it:

find <target_dir> -not -name \*.bz2 -exec bzip2 \{\} \;

i.e. if the dir where the files you want to bzip are is /var/log/blah it would be:

find /var/log/blah -not -name \*.bz2 -exec bzip2 \{\} \;