Difference is it's not done the same way, sidebar is easier, and if you add more categories later the sidebar menu will be updated automatically while the header menu must be updated manually.
First you need to edit each one of your posts, add the appropriate category, uncheck the "Uncategorized" category, update; see here:
http://en.support.wordpress.com/posts/categories/
Then, for a list in the sidebar you simply go to Appearance > Widgets, drag the Categories widget to your sidebar, give it the title you prefer, save.
For a list in the header, you need to replace the top menu of the theme with a custom menu: you go to Appearance > Menus, create a menu, add your pages to it, add a custom link and name it Recipes, make that custom link non-clickable, add your categories, turn them into a dropdown to "Recipes", save the menu, select the menu from the pulldown in the Theme Locations module. Details here:
http://wpbtips.wordpress.com/2011/12/19/custom-menus/