How do I theme a block ?

I would like to theme a specific block.
What is the recommended way to do this using phpTemplate and drupal from CVS ?

I could hack the block.tpl.php file and add tests in it to check for the module name but this does not sound really nice.

To start with, I'd just like to have the search block not display the 'Search' title. Easy ?

I tried to create a block-search.tpl.php file but this doesn't seem to be supported.
Any ideas ?

Thanks in advance.