I've copied the text below from the Gmail Help Center, and added a picture below.
Changing label colors
To change the color of a label:
- In your Labels list, click the square to the right of a label.
- Select a color from the palette that appears. Changes will be instantly reflected in Gmail.
Note: If you don't have any labels yet, first create a label to see the options above.
You can remove a color by selecting Remove color at the bottom of the color palette.