How can I add extra info to my menus?
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().