A $vars array is passed on between all preprocess functions. In case of the _preprocess_page functions, most of the values in $vars are created in template_preprocess_page (see http://api.drupal.org/api/function/template_preprocess_page/6). In that function, you'll see:
$variables['breadcrumb'] = theme('breadcrumb', drupal_get_breadcrumb());
Here, drupal_get_breacrumb returns an array of breadcrumb elements, which is then themed by the theme_breadcrumb() function (or its override).
The easiest way to get what you want is to override the theme_breadcrumb function. To do that, you take the original theme_breadcrumb function (http://api.drupal.org/api/function/theme_breadcrumb/6), copy it to your template.php, replace 'theme' in the function name with the name of your theme and alter the code so it looks like this:
function THEMENAME_breadcrumb($breadcrumb) {
if (count($breadcrumb) > 1) { // This was: if (!empty($breadcrumb))
return '<div class="breadcrumb">'. implode(' » ', $breadcrumb) .'</div>';
}
}
For a better understanding of Drupal theme overrides and preprocess functions, see About overriding themable output and Setting up variables for use in a template (preprocess functions).