What carrier labels were you referring to?
USPS Canadian labels display the order number under the "Invoice/License/Certificate No(s)" field. FedEx International labels can be customized from the label settings page to reflect the order number. At this point, UPS does not allow customization to international labels.
If you are referring to UPS labels, configuring a pick list may be a possible solution. You have the ability to completely customize a pick list to display the orders grouped by order numbers and sorted by the destination country.