Well, you could avoid slicing the image by using an image map to map different parts of the image to different links.
Otherwise you will need to get into the header.php file in your theme, thats where the code that outputs the header image is. If you want to hardcode something, you can do it right there.
/wp-content/themes/[theme-name]/header.php
Here’s a great tool for making that image map.