Steps
Go to Settings
Click on Labels
Click on "Add label"
Add label name, description and colour, then click "Create"
To add it to a conversation:
On the right sidebar of the conversation at Contact/ Conversation Actions, click on "Add label" and select the label you want to add.
