Template file for Views exposed filter block
Actually, although the exposed filter block does not have any template file in the list under Theming information, you can theme it with a views template file like this:

views-exposed-form--MYVIEWNAME.tpl.php

There is an example views-exposed-form.tpl.php in the Views module theme directory.