Things seem to have gotten better/easier since Android 5.0 (API level 21).
I think what you're looking for is something like this:
<style name="AppTheme" parent="AppBaseTheme">
<!-- Top-top notification/status bar color: -->
<!--<item name="colorPrimaryDark">#000000</item>-->
<!-- App bar color: -->
<item name="colorPrimary">#0000FF</item>
</style>
See here for reference:
https://developer.android.com/training/material/theme.html#ColorPalette