To create a new label/folder in Sparrow:

go to Preferences > Organize and click the ‘+’ button.

You can choose the color of your label by clicking the colored square on the left side and picking any color you like from the color wheel.