2
Specifics would have to depend on the theme, but as long as you know where the left column (or main menu) gets rendered, you can insert the image before the <{$block.title}> Smarty tag.
In the default theme, you will have to edit the theme_blockleft.html.
Addendum:
Sorry, I was thinking about the left colum. For the center blocks in the default theme, edit:
theme_blockcenter_c.html
theme_blockcenter_l.html
theme_blockcenter_r.html
I'm not sure though if a fieldset will allow .gifs in the legend area. I suggest converting these divs or fieldsets into a table.