The GPX format is an XML data format designed for lossless storage and transfer of data for GPS devices. As such, it can contain a vast array of very detailed data (such as GPS signal strength, number of visible satelites, etc). The format is available publicly from Topographix and is extensible by using a special extension keyword in its XML. It is used by programs that can match GPS data to events (such as geocoding photos) and is the best choice when you need to move data between GPS devices or when you have needs other than presentation. The format has explicit formats for Routes, Waypoints, and Tracks as distinct data types.
The KML format is a presentation language which was designed for annotating maps. It was originally defined by Keyhole (now Google) and is now a an OGC standards.
How to choose?
Which file format you use is dependent upon what you're trying to do. For people who are looking to preserve the maximum amount of data, make sure you get a GPX file, since they're going to contain all of the information that we downloaded from the device.
If you only need the tracks for Google Earth, then you can just grab the KML. However, it is suggested that if you have any doubt, you get the GPX and the KML (LoadMyTracks will happily convert from GPX to KML, but can't do the other way around) and save the GPX for archival purposes.