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:

  1. In your Labels list, click the square to the right of a label.

    2. Labels Note: If you don't have any labels yet, first create a label to see the options above.

  2. Select a color from the palette that appears. Changes will be instantly reflected in Gmail.

You can remove a color by selecting Remove color at the bottom of the color palette.