I use both gz and bz2 for compression. Both are linux-friendly, so you don't have to worry about that.
Lets compare the two formats:

file.tar.gz : generally larger, but it takes less time to decompress
extraction command: tar -zxvf file.tar.gz

file.tar.bz2: generally smaller, but takes more time to decompress
extraction command: tar -jxvf file.tar.bz2

Now let's assess your needs: If you want to distribute your file online, I reccomend using bz2. This allows for faster downloads of said file. If you are running on a lower-end machine with a faster internet connection, than by all means use gz. This will allow for faster decompression, but download time will suffer.

To conclude: Both formats are (basically) useable accross Linux systems, you just have to decide which format meets your needs best.