A good starting point is (as always) the Codex function reference.
There's one nice little function that can be used to add tags or categories (or whatever built-in or custom taxonomy) to a post:
wp_set_post_terms(); is more easy to use. Further explanation can be found when you follow the link.
There are multiple ways to do this: Bulk adding with fetching all posts (for ex. from a category) with
get_posts(); (or other queries), then looping through all given post objects and adding the needed tags. You could also try to add bulk editing options to your admin UI, but in your case I'd go the easiest way and just write a nice little function that adds your tags to one category and another one to check if it was added. Then proceed to the next category. Writing some custom function that catches all your added tags (true/false) and the check afterwards wouldn't be much. Dumping this into a nice table on shutdown wouldn't hurt:
// the following array can contain any taxonomy. But you have to name it inside wp_set_post_terms. If you need to add tags, use 'post_tag' as 3rd argument.
$tags = array( 'YOUR TAG NAME A HERE', 'YOUR TAG NAME B HERE' );
$args = array( 'post_type' => 'post', 'numberposts' => -1, 'post_status' => published );
$posts = get_posts( $args );
foreach ( $posts as $post )
$check = wp_set_post_terms( intval( $post->ID ), $tags, 'post_tag', true ); // set last value to false if you want to replace existing tags.
$_dump_tag_check[ $post->ID ]['tags'] = $check ? explode( ", ", $tags ) : 'failed';
add_action( 'init', 'wpse31531_add_tags' );
echo '<table><thead><tr><th>Post ID</th><th>Tags</th></tr></thead><tbody>';
foreach ( $GLOBALS['_dump_tag_check'] as $ID => $check )
add_action( 'wpse31531_dump_tag_check', 'shutdown' );
When you read through linked codex pages, you'll see that above code won't work out of the box and is more like a rough guide. It would be highly appreciated if you can edit my answer with your working code for later readers. Thanks.