How and where do I programmatically add a menu to the Navigation menu? I want to add menu items to the Navigation menu dynamically, depending on certain states (example: user is logged in, etc). I assume I do this in theme_preprocess, but I can't seem to find the var to tweak.

Am I looking in the wrong place? Where is the best place to do this, and what is the best method?
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;
}