Custom nav bar styling - iOS
EDIT: This is outdated; for iOS5 there's a much better answer below, by @Jenox.
Completely custom styling for Navigation Bars is surprisingly difficult. The best writeup I know of is this one by Sebastian Celis: http://sebastiancelis.com/2009/12/21/adding-background-image-uinavigationbar/
This doesn't override drawRect, and includes a good explanation why that's a good thing. Also note you don't have to follow his tutorial. You can download the complete code here: https://github.com/scelis/ExampleNavBarBackground
@ludwigschubert's solution does however not work on iOS 5. Neither does overriding -drawRect:, because it isn't even called.
As of iOS 5, a navigation bar consist of a UINavigationBarBackground and a UINavigationItemView. There are two other ways of getting it work.
Insert your custom image view at index 1 instead of 0. This makes it appear above the native background image while staying below the buttons.
Make use of iOS 5's UIAppearance protocol. You can either set the background image for all
[[UINavigationBar appearance] setBackgroundImage:myImage forBarMetrics:UIBarMetricsDefault]
or for just one navigation bar:
[navigationController.navigationBar setBackgroundImage:myImage forBarMetrics:UIBarMetricsDefault]
Make sure to provide two images (UIBarMetricsDefault & UIBarMetricsLandscapePhone) when developing an iPhone app for both portrait and landscape.