Adding menu items programmatically or changing existing menu items?

Sounds like you need to apply the 'menu_name' attribute in hook_menu: http://api.drupal.org/api/drupal/developer--hooks--core.php/function/hoo...

<?php
function my_module_menu()
{
  $menu['logged_in'] = array
  (
    'title' => 'Logged In',
    'page callback' => 'my_logged_in_page',
    'access callback' => 'my_logged_in_access_callback',
    'menu_name' => 'menu-990',
  );
  $menu['logged_out'] = array
  (
    'title' => 'Logged Out',
    'page callback' => 'my_logged_out_page',
    'access callback' => 'my_logged_out_access_callback',
    'menu_name' => 'menu-990',
  );
  return $menu;
}

// The access callback function:
function my_logged_in_access_callback()
{
  return !user_is_anonymous();
}
function my_logged_out_access_callback()
{
  return user_is_anonymous();
}
?>

Ok. While the method you are using to create links works, it's really not the best method as any changes require changes to the template. Drupal's system is set up so that menus can be changed through the admin interface, which means that files don't need to be changed.

What you should do is go to admin -> site building -> menus, and create a menu there (admin interface), then add links to the pages in question. Create a region in your template for the menu to be rendered (template), and then put your menu block in that region (admin interface).

Next. To set the access callback of the menus, you have two options:
1) Change the menu definition using hook_menu_alter(). This allows you to alter the defined menu items. In this you can replace the defined access callback with your own, adding whatever conditions you want (as I showed in the previous posts).
Advantages: The items are not accessible to users who shouldn't be able to access them, even if they directly go to the link.
Disadvantages: Has to be done through code (though only once).
2) Use the menu_per_role module. This module allows you to be able to set visibility of menu items based on role (including anonymous and authorized users).
Advantages: Can be done through the admin interface
Disadvantages: Doesn't actually prevent access to the pages, rather just prevents the links from being rendered in the menu. May also not have enough granularity depending on the conditions under which you want the menu items to be rendered (or not).

To go back to your earlier question:

how do these functions know which menu to apply these conditions to?

By setting the access callback, the links will not be rendered in any menu that is created through the admin interface (see the top of this post). Drupal automatically checks whether users have permission to view the destination page before rendering the item, and if they don't, it won't register the link. This itself is one of the main reasons to use Drupal's menu system, rather than bypassing it as you have by directly outputting the menu in your template.

I hope this all makes things a little clearer!