How do I change the widget header background color?

Go to Theme Options -> CSS and in the CSS Code box add:

.widget .widgettitle {
background-color: #000;
color: #fff;
margin-top: -20px;
padding-top: 15px;
border-radius: 4px 4px 0px 0px;
}

Replace #000 with the colour code you want to use.