There are two things you can do:
In your menu manager, open menu item, then select Metadata tab and change option of Robots field. This won't add rel=nofollow tag to your link, but destination page will have meta tag nofollow.
If you REALLY want to add rel=nofollow, create your menu output template override by:
2.1 Create (if it doesn't exists) templates/YOUR_TEMPLATE/html/mod_menu folder (if folder exists - go to step 2.3)
2.2 Copy ALL files from modules/mod_menu/tmpl to your folder templates/YOUR_TEMPLATE/html/mod_menu
2.3 Open files default_component.php, default_url.php, and override link by adding rel="nofollow" where tags are built.
Hope it helps ;)