How to add post count to wp_nav_menu?

Basically the easiest thing should be a callback to the start_el() method of the Walker class.

// From core:
apply_filters( 'walker_nav_menu_start_el', $item_output, $item, $depth, $args );

Just grab the data (whatever the actual data is and from wherever it comes) and append it.

add_action( 'walker_nav_menu_start_el', 'wpse_10042_nav_menu_post_count', 10, 4 );
function wpse_10042_nav_menu_post_count( $output, $item, $depth, $args )
{
    // Check $item and get the data you need
    printf( '<pre>%s</pre>', var_export( $item, true ) );
    // Then append whatever you need to the $output
    $output .= '';

    return $output;
}