@implementation UINavigationBar (CustomImage)
- (void)drawRect:(CGRect)rect {
	UIImage *image = [UIImage imageNamed: @"NavigationBar.png"];
	[image drawInRect:CGRectMake(0, 0, self.frame.size.width, self.frame.size.height)];
}
@end

http://discussions.apple.com/thread.jspa?threadID=1649012&tstart=0

This works well for me, and doesn't appear to have issues with pushing new view controllers, hidden titles and bar button items, etc. 

To implement it just copy and paste this line before you ViewController @implementation file.  Example:

//
//  MenuViewController.m
//  Restaurant
//
//  Created by Eddie on 4/10/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

#import "MenuViewController.h"
#import "CheckoutViewController.h"

@implementation UINavigationBar (CustomImage)
- (void)drawRect:(CGRect)rect {
	UIImage *image = [UIImage imageNamed: @"grayGB.png"];
	[image drawInRect:CGRectMake(0, 0, self.frame.size.width, self.frame.size.height)];
}
@end


@implementation MenuViewController

@synthesize tableView,
			menuArray;

Custom background for UINavigationBar

Objective C