Caso esteja utilizando a AppCompat Material Design, você definirá pela cor primária:

    <style name="AppTheme" parent="Theme.AppCompat.Light">
       <item name="colorPrimary">@color/material_blue_grey_900</item>
    </style>

Caso contrário (APIs anteriores a partir do 3.0), use no atributo parent da sua ActionBar o estilo vindo de Widget, por exemplo:
        
    <style name="MyActionBar" parent="@style/Widget.AppCompat.Light.ActionBar">