Instead of using the normal method

- (NSString *)tableView:(UITableView *)tableView titleForHeaderInSection:(NSInteger)section

You want to implement this one:

- (UIView *)tableView:(UITableView *)tableView viewForHeaderInSection:(NSInteger)section

As you can see, the second one returns a UIView instead of just string for text. Therefore you can customise your own view (with labels etc) and return it.

Here is an example of how you might do that (to be implemented in the above method:

// create the parent view that will hold header Label 
UIView* customView = [[[UIView alloc] initWithFrame:CGRectMake(10,0,300,60)] autorelease]; 

// create image object
UIImage *myImage = [UIImage imageNamed:@"someimage.png"];

// create the label objects 
UILabel *headerLabel = [[[UILabel alloc] initWithFrame:CGRectZero] autorelease];
headerLabel.backgroundColor = [UIColor clearColor];
headerLabel.font = [UIFont boldSystemFontOfSize:18];
headerLabel.frame = CGRectMake(70,18,200,20);
headerLabel.text = @"Some Text"; 
headerLabel.textColor = [UIColor redColor]; 

UILabel *detailLabel = [[[UILabel alloc] initWithFrame:CGRectZero] autorelease]; 
detailLabel.backgroundColor = [UIColor clearColor]; 
detailLabel.textColor = [UIColor darkGrayColor]; 
detailLabel.text = @"Some detail text"; 
detailLabel.font = [UIFont systemFontOfSize:12]; 
detailLabel.frame = CGRectMake(70,33,230,25); 

// create the imageView with the image in it 
UIImageView *imageView = [[[UIImageView alloc] initWithImage:myImage] autorelease]; 
imageView.frame = CGRectMake(10,10,50,50); 
[customView addSubview:imageView]; 
[customView addSubview:headerLabel]; 
[customView addSubview:detailLabel]; 
return customView;