Go to the Orders/Labels menu option and click the Add new label.

Label Display Name (internal)
Specify a display name that will be used for internal purposes in your admin. This name is never displayed to your customer. You can use a more specific label name for internal purposes.

Email Customer on change?
If you enable this option, an email will automatically be sent to the customer notifying them of an update of status when it is applied to an order.

Label Display Name (external)
Specify a display name that your customer will see. This display name is provided on order update notifications and within the account management on your store. If nothing is provided and an order is in the selected state, the customer display will be a generic "Processing" status.

Label Color
Choose a color for your label for easy identification from within the order management admin.

You can apply or remove a label on an order from the order details action button or from the order management action button.