One method would be to alter the exposed filter form date_select form element. Add this to a custom module:
/**
* Implements hook_form_alter().
*/
function MYMODULE_form_views_exposed_form_alter(&$form, $form_state, $form_id) {
$form['#after_build'][] = 'views_exposed_form_date_select_alter';
}
/**
* Alter the label option on Year/Month selector
*/
function views_exposed_form_date_select_alter($form, &$form_state) {
$form['MY_DATE_FIELD']['year']['#options'][''] = 'Year';
$form['MY_DATE_FIELD']['month']['#options'][''] = 'Month';
return $form;
}