The easiest way to apply wallpaper and bar colors is with the MS Theme Generator, which is free and runs on your PC.
ICBar or Wisbar both allow you to skin the Navigation bar ... using graphics for the bar wallpaper as well as seperate images for the buttons.
The elements of the nav bar are all custom images.
