There are several different "versions" in the Trading API. How are they related?

There are a couple notions of "version" in your case. One is the "API version" discussed here :
http://developer.ebay.com/DevZone/XML/docs/Reference/eBay/AddItem.html#Request.Version
http://developer.ebay.com/DevZone/XML/docs/HowTo/eBayWS/eBaySchemaVersioning.html

Another type of version is CategoryVersion in the GetCategories call :
http://developer.ebay.com/DevZone/XML/docs/Reference/eBay/GetCategories.html#Response.CategoryVersion

In general, these three versions are independent of each other.

For example, eBay releases new versions of the API every two weeks. There may be more or fewer iterations of CategoryVersion and AttributeSystemVersion in the same time span.