Is there a way to programmatically add new links to the primary links? Is there a way to add links to the primary links using PHP in Drupal 6? The reason I ask is that I want to add more links in the footer of the web page, which I don't want to put in the top navigation level.
You can either specifiy the menu name in hook_menu() (look for 'menu_name') if they are defined with that hook or you can use menu_link_save().

Yet another option would be to use http://drupal.org/project/features and export your menu structure as a feature.