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' =&gt; 'user_is_anonymous',  //or 'user_is_logged_in' to check if logged in
   'type' =&gt; MENU_NORMAL_ITEM,
   'menu_name' =&gt; 'navigation',
   'title' =&gt; t('Title of Menu Item'),
  );
  return $items;
}