Until Gmail adds an option to create your own themes, you can edit the colors from Gmail's default theme. Go to the Themes section from Gmail's settings, click on "Choose your own colors" and select your favorite colors for Gmail's background, links, text messages, navigation links and more.
Your colors are saved when you finish editing the theme and the changes are added to Gmail after you press "Save". If you don't like your theme, you can always choose one of the 31 pre-defined thems or click on "Reset" to go back to the default theme.
"Companies that use Google Apps won't see the options for themes yet, but we're working on getting themes to you too," mentions Gmail's blog.