How do I add divs to a sitemap?
You can use theme_site_map_box in your template.php!

I've done something similar before where I've changed the H2's to H3's:

Try something like the following in your template.php

function MYTHEME_site_map_box($variables) {
  $title = $variables['title'];
  $content = $variables['content'];
  $attributes = $variables['attributes'];

  $output = '';
  if (!empty($title) || !empty($content)) {
    $output .= '&lt;div' . drupal_attributes($attributes) . '&gt;';
    if (!empty($title)) {
      $output .= '&lt;h3 class="title"&gt;' . $title . '&lt;/h3&gt;';
    }
    if (!empty($content)) {
      $output .= '&lt;div class="content"&gt;&lt;div class="MYCLASS"&gt;' . $content . '&lt;/div&gt;&lt;/div&gt;';
    }
    $output .= '&lt;/div&gt;';
  }

  return $output;
}


I can't remember off the top of my head the structure of $content, but the above code should put an extra div around each section of the site map with the class of MYCLASS.

API Docs: theme_site_map_box()