Label for Child in Hierarchical Select
I know I'm late, because this answer has been answered long time ago, but I don't think this is the right way to do it, especially with the java script interval function – it might work but in many cases may cause a problem.

For those who need the same result I suggest to use this java script code which is based on action when the ajaxStop event is triggered.

First you nedd to create a java script file in your module directory, for exapmle: YOUR_MODULE_NAME/js/custom_shs_behaviors.js with the following code:

/**
 * @file
 * Custom behaviors for Simple hierarchical select:
 *   Change the first option text from "- None -" to whatever you want (default: "- Any -").
 *   Create labels for each level.
 */
 (function($) {
  Drupal.behaviors.customShsBehaviors = {
    attach: function (context, settings) {

      // Helper function for an option text replacement.
      // use: optionObj.replaceOptionText(); for default replacement from '- None -' to '- Any -'.
      // or optionObj.replaceOptionText('Foo'); to replace the '- None -' with 'Foo'.
      $.fn.replaceOptionText = function(replacement) {
        var replacement = replacement ? replacement : '- Any -';
        if ($(this).text() == Drupal.t('- None -')) {
          $(this).text(Drupal.t(replacement));
        }
      };

      // Function that helps to get the select element width including its padding and margin.
      $.fn.getSelectWidth = function() {
        var width = Math.round($(this).wrap('&lt;span&gt;&lt;/span&gt;').outerWidth(true));
        $(this).unwrap();
        return width;
      }

      // Define labels.
      var labels = ['Label-1', 'Label-2', 'Label-3'];

      // act when the ajaxStop event is triggered (there are no more Ajax requests being processed.)
      // see: @link http://api.jquery.com/Ajax_Events/ @endlink
      $('.shs-wrapper-processed').ajaxStop(function(event, xhr, settings) {

        $("select.shs-select").each(function(level) {

          // fix the SHS bug - new level that is being created has the same ID as the previous one.
          // make sure that each select has an ID and the class corresponding to the level.
          // YOU CAN USE THESE TWO LINES ONLY IF YOU ARE USING SHS WITH THE ABILITY TO ADD NEW LEVELS.
          $(this).attr('id', $(this).attr('id').replace(/(.*)select-(\d+)/, "$1select-" + (level+1)));
          $(this).attr('class', $(this).attr('class').replace(/(.*)level-(\d+)/, "$1level-" + (level+1)));

          // Replace the first option text using the helper function for an option text replacement.
          $("option", this).first().replaceOptionText();

          // Get label width.
          var labelWidth = $(this).getSelectWidth();

          // Create label.
          if ($("label[for='" + $(this).attr('id') + "']").length == 0) {
            $(this).parent().before(
              "&lt;label for='" + $(this).attr('id') + "' style='display: inline-block; width: " + labelWidth + "px'&gt;" + labels[level] + "&lt;/label&gt;"
            );
          }

          // Remove the label if the select element has just been removed by clicking any option on lower level.
          // There might be several Ajax requests bound with this action,
          // so we have to make sure that our "removing process" will be executed at most once.
          // See: @link http://api.jquery.com/one/ @endlink
          $("option:not(:selected)", this).one("click", function() {
            $(".shs-wrapper-processed").parent().find("label").each(function() {
              if ($(this).attr('for').slice(-1) &gt; level+1) {
                $(this).remove();
              }
            });
          });
        });
      });
    }
  };
})(jQuery);


And attach the java script file to your form. You can do it by using the hook_form_alter() in your theme or module file:

/**
 * Implements hook_form_alter.
 */
function YOUR_MODULE_NAME_form_alter(&amp;$form, &amp;$form_state, $form_id) {

  switch($form['#id']) {
    case 'YOUR-FORM-ID' :
      $form['#attached']['js'][] = drupal_get_path('module', 'YOUR_MODULE_NAME') . '/js/custom_shs_behaviors.js';
    break;
  }
}


You're done! With this code you can set the label for each level of your shs and even change the default option text, for example: from - none -  to - any -.