1. In Admin>Layout put the code in one of the boxes (e.g. HTML in sidebar on each page). Alternatively try Widget Anywhere plugin for more options.
2. Create an advanced theme, override the search() function to make the form go to Google.
3. Make a new image and overwrite the current logo (under qa-theme/Snow) or change the CSS file to point to the new image.
4. Override the header() function in your theme, find the category (sorry, not sure exactly how from memory) and do a switch on the category and output a different header for each one.
5. Not sure exactly what you mean but you would override a function in the theme and put your code there instead of the current menu.