How do "Order Types" and "Order Item Types" work?
What rules does Drupal use to decide which Order Type it's dealing with?

That's determined by order type resolvers (implementing OrderTypeResolverInterface in this case). Such resolvers are given an order item, and must use that to determine the type of order.
Out of the box, the default resolver (DefaultOrderTypeResolver) uses the bundle of the given order item, which will be an order item type ID, to load that item type entity, and get the associated order type ID from it.

At what point in the is this decision made?

There are probably multiple places that decision is made (creating orders in the admin UI for example), but in terms of the cart, it happens when the cart is created, which in turn happens when an item is first added to it via the standard AddToCartForm submission.
So I think it's fair to say that the type of an order that originated from a cart will always be the type associated with the first item that was added to it.