How can I add extra info to my menus? I have some menus that are managed in the standard Menus module (Drupal 6, BTW). I want to add a checkbox when I'm editing a menu item to control the display of a "New" banner via CSS (by adding a class for items that have the checkbox turned on).

I can get my checkbox into the form like so:

function mymodule_form_menu_edit_item_alter(&amp;$form, &amp;$form_state) {
  $form['menu']['newbanner'] = array(
    '#title' =&gt; 'New banner',
    '#type' =&gt; 'checkboxes',
    '#description' =&gt; "Add a 'New' banner to this item?",
    '#options' =&gt; array( 'new_banner' =&gt; t("This item is new") )
    );
}


But I'm not quite sure how to actually save and use the state of my checkbox. I'm guessing I want to start by creating a mymodule_form_menu_edit_item_submit() function? But how do I get my info in/out of the database and use it to add a class to the generated menu on the front-end?
The code you wrote so far is correct; you just need to add the code for getting the saved setting, and the code to save it.

function mymodule_form_menu_edit_item_alter(&amp;$form, &amp;$form_state) {
  // Get the mlid ID of the menu item.
  $mlid = $form['menu']['mlid']['#value'];

  $form['menu']['newbanner'] = array(
    '#title' =&gt; 'New banner',
    '#type' =&gt; 'checkboxes',
    '#description' =&gt; "Add a 'New' banner to this item?",
    '#default_value' =&gt; variable_get("mymodule_newbanner_$mlid", 0),
    '#options' =&gt; array('new_banner' =&gt; t("This item is new")),
  );

  $form['#submit'][] = 'mymodule_menu_item_submit';
}

function mymodule_menu_item_submit($form, &amp;$form_state) {
  $item = &amp;$form_state['values']['menu'];
  // Get the last ID inserted in the table.
  if (empty($item['mlid'])) {
    $item['mlid'] = db_last_insert_id('menu_links', 'mlid');
  }

  variable_set('mymodule_newbanner_' . $item['mlid'], $item['newbanner']);
}


The mlid could be zero, when the menu item is first created; in that case, the form submission handler gets it from the table, as it is executed after the form submission handler added by menu.module, which saves the menu item in the table using menu_link_save().