Copy block.tpl.php to block-uc_cart.tpl.php and modify that new file - you won't need the check on the module name or delta.

Copy the theme function into template.php (Found in the same directory as block.tpl.php. If not, just create it.) Edit template.php and change the "theme_" in the function name to be "yourthemename_". Then modify the code in the function to emit the HTML you want. You might also need to override theme_uc_cart_block_title in this same manner.