I don't have a copy of a 3 columns nefty_corners, but look in the style.css for something similar to.... which contains the image...

div.pageHeader /* Title zone */
{
	margin: 0 1ex;
	padding: 0;
	background-image: url(rsc/img/squares.gif);
	background-repeat: no-repeat;
	background-position: right center;
	/* border: 1px solid #f00; */
}

I found that but it only refrences the squares.gif which is but a small part of the header. I need to remove and replace the entire header. Any ideas on how to do that?

That is the pageHeader div, you can style it however you like, simply edit the css, replace the squares.gif with your image and align it as you need.

I think I figured out how to do it but I am still confused on where to put the navigation that will be going immediately under my header. It says to not put it in the overall_header_inc - is there a reason for that? If so where is it suggested that navigation be put - I will be using custom buttons and mouseovers.