Here's something I came up with after applying a few principles other SO posts, including Aaron's link:
AnnotationPin *myAnnotation = (AnnotationPin *)annotation;
self = [super initWithAnnotation:myAnnotation reuseIdentifier:reuseIdentifier];
self.backgroundColor = [UIColor greenColor];
self.frame = CGRectMake(0,0,30,30);
imageView = [[UIImageView alloc] initWithImage:myAnnotation.THEIMAGE];
imageView.frame = CGRectMake(3,3,20,20);
imageView.layer.masksToBounds = NO;
[self addSubview:imageView];
[imageView release];
CGSize titleSize = [myAnnotation.THETEXT sizeWithFont:[UIFont systemFontOfSize:12]];
CGRect newFrame = self.frame;
newFrame.size.height = titleSize.height + 12;
newFrame.size.width = titleSize.width + 32;
self.frame = newFrame;
self.layer.borderColor = [UIColor colorWithRed:0 green:.3 blue:0 alpha:1.0f].CGColor;
self.layer.borderWidth = 3.0;
UILabel *infoLabel = [[UILabel alloc] initWithFrame:CGRectMake(26,5,newFrame.size.width-32,newFrame.size.height-12)];
infoLabel.text = myAnnotation.title;
infoLabel.backgroundColor = [UIColor clearColor];
infoLabel.textColor = [UIColor blackColor];
infoLabel.textAlignment = UITextAlignmentCenter;
infoLabel.font = [UIFont systemFontOfSize:12];
[self addSubview:infoLabel];
[infoLabel release];
In this example, I'm adding a custom pin to a MKAnnotation class that resizes a UILabel according to the text size. It also adds an image on the left side of the view, so you see some of the code managing the proper spacing to handle the image and padding.
The key is to use CGSize titleSize = [myAnnotation.THETEXT sizeWithFont:[UIFont systemFontOfSize:12]]; and then redefine the view's dimensions. You can apply this logic to any view.
Although Aaron's answer works for some, it didn't work for me. This is a far more detailed explanation that you should try immediately before going anywhere else if you want a more dynamic view with an image and resizable UILabel. I already did all the work for you!!