This shouldn't have been as hard to figure out as it was, so I'm blogging it for Google: Files that end in the extension .bz2 are files compressed with bzip2 (or something that uses libbzip2). bzip2 comes with RedHat Linux, but doesn't typically come with other distributions.

Hooray for WikiPedia for being there when Google couldn't give me a straight answer. WikiPedia on bzip2; WikiPedia's list of file formats.