Drupal - How and where do I programmatically add a menu to the Navigation menu?

I'd suggest checking out hook_menu(). For example, the following implementation of hook_menu() placed in either a module or template.php should insert a menu item into the navigation menu for anonymous users. Take a look at the User module for some good examples of how to implement hook_menu() for different user roles.

function MODULE_menu() {
   $items = array();
   $items['the/menu/path'] = array(
   'access callback' => 'user_is_anonymous',  //or 'user_is_logged_in' to check if logged in
   'type' => MENU_NORMAL_ITEM,
   'menu_name' => 'navigation',
   'title' => t('Title of Menu Item'),
  );
  return $items;
}

I think you can create it by using menu_link_save().

$item = array(
  'link_path' => 'my_path',
  'link_title' => 'title',
  'menu_name' => 'header-top-menu', // Menu machine name, for example: main-menu
  'weight' => 0,
  'language' => $node->language,
  'plid' => 0, // Parent menu item, 0 if menu item is on top level
  'module' => 'menu',
);
menu_link_save($item);

You could use the code I am showing in a hook_update_N() implementation.

See also Drupal 7 Menu Link update through update.php.