What USB drive filesystem works out of the box on Windows, Linux, and OS X?

Update 2018-05-25: Since I initially wrote this answer in 2015, exFAT has continued to grow in popularity, largely due to the similarly increasing popularity of SDXC and the need for a modern cross-platform filesystem. At least two Ubuntu flavors, Kylin (desktop) and MATE (core + desktop), include exFAT support by default as of 18.04. It's still patent-encumbered, but, then again, so is the rest of the FAT family. Some people think they can work around these patents; others have tried challenging them, with little success.

The FAT series of filesystems tends to be the most widely supported on modern day operating systems. It’s a very simple filesystem, and a basic implementation can be written quickly for any platform. FAT16 is probably the most widely supported variety, followed closely by FAT32. For a 64 GB drive, FAT32 would be ideal. As others have mentioned, the catch is that you'd need to use a third party utility to format the partition if you're using Windows because the built-in Windows utility can’t create FAT32 partitions larger than 32 GB. Additionally, FAT32 can't store files larger than 4 GiB, since the size of each file is stored as a 32-bit unsigned integer. FAT32 is probably your best bet if you can tolerate the initial hassle of formatting the drive and the file size limit.

exFAT is starting to see more widespread use, particularly on mobile platforms, as it’s a standard format for large SD cards (SDXC). You'll likely find native support for exFAT on any device with an SDXC card reader. As you've noticed, some platforms—or specific versions/distros of platforms—don’t ship the drivers by default, usually because the distro chooses to avoid “non-free” software. The entire FAT family is patent-encumbered, but exFAT has the most recent patents of the group (e.g., US8321439 and US8583708), most of which won't expire for a long time. My recommendation would be to use exFAT if FAT32 is too restrictive, particularly if you’ll often be using the drive on Windows. Yes, you may need to install drivers on some Linux systems, but they are useful drivers that should probably be installed anyway, and the patent concerns are unlikely to be an issue for individual users.

Formatting the drive as UDF would overcome some of the limitations of FAT32. However, some platforms are likely to present the device to the user as an optical drive, which could be cumbersome. You’d also probably need a third-party utility to format the drive on Windows or Mac. If you go this route, make sure to use plain UDF, rather than VAT or spared. The latter two builds are for certain types of optical media and won’t work as expected on a flash drive. Allegedly, UDF doesn’t support files larger than 1GB on Linux due to a lazy fix for a security vulnerability (CVE-2006-4145)—I haven’t verified this. There’s also some evidence to indicate that Windows may outright refuse to handle non-optical media formatted as UDF, but I haven’t tested this either.

I would recommend the FAT32 filesystem.

The FAT32 filesystem works out of the box on almost all OSes. Most USB flash drives come preformatted as FAT32.

You will have to make 2 partitions on the USB, and they will only be visible on Linux or Mac. This is because FAT32 can only handle 32GB partition sizes at most. In Windows, it will only show the first partition.

FAT can only handle partition sizes of 4GB, so I would not recommend it because as I said Windows will only show the first partition.

NTFS needs additional drivers on Linux and Mac, and you may run into problems with file permissions.

UDF is supported by most modern operating systems and does not have the severe limitations of FAT32. See the compatibility table on Wikipedia.