I believe this is documented in Drupal's [Form API Reference](http://api.drupal.org/api/drupal/developer!topics!forms_api_reference.html/6#checkboxes).

You should be able to set the labels corresponding to each checkbox in the **#options** array. The array can be of the format:

    array(
      'submitted_value1' => t('Label 1'),
      'submitted_value2' => t('Label 2'),
    );

Each key of the array is the value that will be submitted when the form is submitted. The value of each element in the array is what is displayed.