How do I set the print order for address labels?
It is complicated to add a sort order on address labels. I think it is possible to add a sort order to your search and that sort order is used in printing labels. 

However, in a recent project, we dealt with the exact problem and using the search did not do the trick. I don't know why anymmore. But we solved the problem by creating a custom report template which they are using for their address labels. 

You can find an example of such a report at https://github.com/SPnl/nl.sp.bezorggebieden/blob/master/CRM/Bezorggebieden/Form/Report/Tribune/AddressLabel.php#L251 
I have added a line marker that is where the processing of the report to PDF starts. 
This address label report has additional features such as starting on a new page as soon as a switch of a local chapter starts. (This organisation sends sheets with address labels to local chapters).