How do I format my external hard drive to a very Linux compatible file system?
You could use GUI applications like GParted on Ubuntu. Install them from the repositories using:
Once you have it installed, select the correct block device/partition and format it using a filesystem like ext2/3/4, JFS, XFS, ResiserFS, etc depending on your needs.
However, the above mentioned file systems are only for reference. Not all of them run on all distributions perfectly.
For example, as @Nils pointed out:
Ext2 is almost a legacy file system now and not a very good choice.
That leaves only Ext3 and Ext4.
Again, since ext4 is still new and under development, it may have problems with a few distributions. For example, on RH5 there is no ext4, on SLES10 it is a bit dicey. However, I should point out here that the vanilla Linux kernel completely supports ext4 since version 2.6.28. On Arch and Gentoo ext4 gives no problems.
But ext3 will work an any current distribution - not only the newest ones.
Since it is an external drive, you might want to format with Fat32 or NTFS, so you access the files when moving the disk around to different platforms.
As darnir said, Gparted is a suitable tool for this.