It’s completely up to you. You can either put them in the header or not, as long as the elements within them are internal navigation elements only (i.e. don’t link to external sites such as a twitter or facebook account) then it’s fine.
They tend to get placed in a header simply because that’s where navigation often goes, but it’s not set in stone.
You can read more about it at HTML5 Doctor.