I am assuming this is for the built-in Category taxonomy for Posts? This would be the way of doing it.
add_action( 'registered_taxonomy', 'my_custom_category_paragraph', 10, 3 );
function my_custom_category_paragraph( $taxonomy, $object_type, $args ) {
global $wp_taxonomies;
if ( 'category' !== $taxonomy )
return;
// Change the callback that renders the metabox with our own.
$wp_taxonomies[$taxonomy]->meta_box_cb = 'my_category_metabox_paragraph';
}
function my_category_metabox_paragraph( $post, $box ) {
// add our paragraph here
echo '<p>Hi there, sailor!</p>';
// Call the default meta box function
post_categories_meta_box( $post, $box );
}