How do I add a span "wrapper" to all required form fields?
I'd suggest you create an implementation of the theme hook form_element, to add a new class at the top level rather than an extra div which is simply redundant. That way you don't have to recursively process every form on the site looking for required fields. Unfortunately the standard form_element implementation is not designed in a very helpful way, so you have to duplicate a lot of code:

  function mymoduleortheme_form_element($variables) {
    $element = &amp;$variables['element'];
    // This is also used in the installer, pre-database setup.
    $t = get_t();

    // This function is invoked as theme wrapper, but the rendered form element
    // may not necessarily have been processed by form_builder().
    $element += array(
      '#title_display' =&gt; 'before',
    );

    // Add element #id for #type 'item'.
    if (isset($element['#markup']) &amp;&amp; !empty($element['#id'])) {
      $attributes['id'] = $element['#id'];
    }
    // Add element's #type and #name as class to aid with JS/CSS selectors.
    $attributes['class'] = array('form-item');
    // extra code here ---&gt;
    if(!empty($element['#required'])) {
      $attributes['class'][] = 'form-element-required';
    }
    // &lt;---
    if (!empty($element['#type'])) {
      $attributes['class'][] = 'form-type-' . strtr($element['#type'], '_', '-');
    }
    if (!empty($element['#name'])) {
      $attributes['class'][] = 'form-item-' . strtr($element['#name'], array(' ' =&gt; '-', '_' =&gt; '-', '[' =&gt; '-', ']' =&gt; ''));
    }
    // Add a class for disabled elements to facilitate cross-browser styling.
    if (!empty($element['#attributes']['disabled'])) {
      $attributes['class'][] = 'form-disabled';
    }
    $output = '&lt;div' . drupal_attributes($attributes) . '&gt;' . "\n";

    // If #title is not set, we don't display any label or required marker.
    if (!isset($element['#title'])) {
      $element['#title_display'] = 'none';
    }
    $prefix = isset($element['#field_prefix']) ? '&lt;span class="field-prefix"&gt;' . $element['#field_prefix'] . '&lt;/span&gt; ' : '';
    $suffix = isset($element['#field_suffix']) ? ' &lt;span class="field-suffix"&gt;' . $element['#field_suffix'] . '&lt;/span&gt;' : '';

    switch ($element['#title_display']) {
      case 'before':
      case 'invisible':
        $output .= ' ' . theme('form_element_label', $variables);
        $output .= ' ' . $prefix . $element['#children'] . $suffix . "\n";
        break;

      case 'after':
        $output .= ' ' . $prefix . $element['#children'] . $suffix;
        $output .= ' ' . theme('form_element_label', $variables) . "\n";
        break;

      case 'none':
      case 'attribute':
        // Output no label and no required marker, only the children.
        $output .= ' ' . $prefix . $element['#children'] . $suffix . "\n";
        break;
    }

    if (!empty($element['#description'])) {
      $output .= '&lt;div class="description"&gt;' . $element['#description'] . "&lt;/div&gt;\n";
    }

    $output .= "&lt;/div&gt;\n";

    return $output;
  }