example.m

UINavigationController *navCon = ...;

UIImage *background = [UIImage imageNamed:@"navigationBar.png"];
UIImageView *img = [[UIImageView alloc] initWithImage:background];

[navCon.navigationBar insertSubview:img
                            atIndex:-1];

[img release];

UINavigationBar+CustomBackground.h

@interface UINavigationBar (CustomBackground)

- (void)insertSubview:(UIView *)view atIndex:(NSInteger)index;

@end

UINavigationBar+CustomBackground.m

@implementation UINavigationBar (CustomBackground)

- (void)insertSubview:(UIView *)view atIndex:(NSInteger)index
{
    [super insertSubview:view atIndex:index+1];
}

@end

UINavigationBarCustomBackground.h

@interface UINavigationBar (CustomBackground)

- (void)insertSubview:(UIView *)view atIndex:(NSInteger)index;

@end

UINavigationBarCustomBackground.m

@implementation UINavigationBar (CustomBackground)

- (void)insertSubview:(UIView *)view atIndex:(NSInteger)index
{
    [super insertSubview:view atIndex:index+1];
}

@end