It can be done inside styles.xml using
<item name="android:navigationBarColor">@color/theme_color</item>
or
window.setNavigationBarColor(@ColorInt int color)
http://developer.android.com/reference/android/view/Window.html#setNavigationBarColor(int)
Note that the method was introduced in Android Lollipop and won't work on API version < 21.
The second method (works on KitKat) is to set windowTranslucentNavigation to true in the manifest and place a colored view beneath the navigation bar.