To get headings above links, add this (modified appropriately) to each desired link display block:
PHP Code:

        $content 
.= '<span class="catBoxHeading1">' . (file_exists(DIR_WS_TEMPLATE_IMAGES 'cathead-featured.gif') ? zen_image(DIR_WS_TEMPLATE_IMAGES 'cathead-featured.gif') . '</span>':'Link Heading</span>' $disp_block_head) . "\n";// categories dressing - uncomment this line for heading above link 
Or simply replace the entire last section of tpl_categories.php with this:
PHP Code:

  
if (SHOW_CATEGORIES_BOX_SPECIALS == 'true' or SHOW_CATEGORIES_BOX_PRODUCTS_NEW == 'true' or SHOW_CATEGORIES_BOX_FEATURED_PRODUCTS == 'true' or SHOW_CATEGORIES_BOX_PRODUCTS_ALL == 'true') {
// display a separator between categories and links
    
if (SHOW_CATEGORIES_SEPARATOR_LINK == '1') {
      
$content .= '<hr id="catBoxDivider" />' "\n";
    }
    if (
SHOW_CATEGORIES_BOX_SPECIALS == 'true') {
      
$show_this $db->Execute("select s.products_id from " TABLE_SPECIALS " s where s.status= 1 limit 1");
      if (
$show_this->RecordCount() > 0) {
        
//$content .= '<span class="catBoxHeading1">' . (file_exists(DIR_WS_TEMPLATE_IMAGES . 'cathead-specials.gif') ? zen_image(DIR_WS_TEMPLATE_IMAGES . 'cathead-specials.gif') . '</span>':'Link Heading</span>' . $disp_block_head) . "\n";// categories dressing - uncomment this line for heading above link 
        
$content .= '<a class="category-links" href="' zen_href_link(FILENAME_SPECIALS) . '">' CATEGORIES_BOX_HEADING_SPECIALS '</a>' $disp_block "\n";
      }
    }
    if (
SHOW_CATEGORIES_BOX_PRODUCTS_NEW == 'true') {
      
// display limits
//      $display_limit = zen_get_products_new_timelimit();
      
$display_limit zen_get_new_date_range();

      
$show_this $db->Execute("select p.products_id
                                 from " 
TABLE_PRODUCTS " p
                                 where p.products_status = 1 " 
$display_limit " limit 1");
      if (
$show_this->RecordCount() > 0) {
        
//$content .= '<span class="catBoxHeading1">' . (file_exists(DIR_WS_TEMPLATE_IMAGES . 'cathead-new.gif') ? zen_image(DIR_WS_TEMPLATE_IMAGES . 'cathead-new.gif') . '</span>':'Link Heading</span>' . $disp_block_head) . "\n";// categories dressing - uncomment this line for heading above link 
        
$content .= '<a class="category-links" href="' zen_href_link(FILENAME_PRODUCTS_NEW) . '">' CATEGORIES_BOX_HEADING_WHATS_NEW '</a>' $disp_block "\n";
      }
    }
    if (
SHOW_CATEGORIES_BOX_FEATURED_PRODUCTS == 'true') {
      
$show_this $db->Execute("select products_id from " TABLE_FEATURED " where status= 1 limit 1");
      if (
$show_this->RecordCount() > 0) {
        
$content .= '<span class="catBoxHeading1">' . (file_exists(DIR_WS_TEMPLATE_IMAGES 'cathead-featured.gif') ? zen_image(DIR_WS_TEMPLATE_IMAGES 'cathead-featured.gif') . '</span>':'Link Heading</span>' $disp_block_head) . "\n";// categories dressing - uncomment this line for heading above link 
        
$content .= '<a class="category-links" href="' zen_href_link(FILENAME_FEATURED_PRODUCTS) . '">' CATEGORIES_BOX_HEADING_FEATURED_PRODUCTS '</a>' $disp_block "\n";
      }
    }
    if (
SHOW_CATEGORIES_BOX_PRODUCTS_ALL == 'true') {
      
//$content .= '<span class="catBoxHeading1">' . (file_exists(DIR_WS_TEMPLATE_IMAGES . 'cathead-all.gif') ? zen_image(DIR_WS_TEMPLATE_IMAGES . 'cathead-all.gif') . '</span>':'Link Heading</span>' . $disp_block_head) . "\n";// categories dressing - uncomment this line for heading above link 
      
$content .= '<a class="category-links" href="' zen_href_link(FILENAME_PRODUCTS_ALL) . '">' CATEGORIES_BOX_HEADING_PRODUCTS_ALL '</a>' "\n";
    }
  }
  
$content .= '</div>';
?> 
Replace "Link Heading" with your desired text.
If you want images instead of text for these headings, name them like cathead-featured.gif and save them in /your_template/images/.

This code will check to see if an appropriately-named file exists, and if so, display it; if not, display the heading text at the end of the statement.
To disable any heading, comment out its line as noted.

This and similar more robust and flexible code for category headings will be in the next release of Categories Dressing.