How can I modify the WordPress default widget output?

To expand on Mark’s answer, there’s not much (generally) available in the way of filters in the default WordPress widgets (except for perhaps widget_text).

But adding your own custom widget is easy – put this in your functions.php:

require_once("my_widget.php");
add_action("widgets_init", "my_custom_widgets_init");

function my_custom_widgets_init(){
  register_widget("My_Custom_Widget_Class");
}

Then you simply want to copy the existing categories widget from wp-includes/widgets/class-wp-widget-categories.php to my_widget.php in your theme, and change the class name to the same name as that used in the call to register_widget() above.

Then make whatever changes you like! I suggest changing the title too so you can distinguish it from the default Categories widget.