Just to clarify, and based on what you are saying, you want to customise the look of the CALLOUT bubble that shows title/subtitle, not the annotation view itself, is this correct?
In case you're not clear, the MKAnnotationView is basically the image/icon/button that you see on top of the map for a specific location. Once you tap on that image/icon, if enabled, a call out bubble will appear where you can set a view for the left hand side, title, subtitle and a view for the right hand side - is this what you are hoping to customise?
If that's the case, this is a non-trivial task and if you are new to iPhone development chances are this is going to take a long time for you to implement.
If you still want to have a look, here's a blog post that might be of interest to you... http://blog.asolutions.com/2010/09/building-custom-map-annotation-callouts-part-1/