A lot depends on what you want to encourage, and on what your business model is.
If you have a Contact Us link in your header (all else being equal), it is more likely that someone will contact you. So if that is key to your business strategy, then put it in your header. Companies for which their customer service / contacts are actually an important sales method usually do this. Zappos is an example of this.

Not all companies put a Contact Us link in the header. Companies that don't really want you to contact them, as it is a business strain, typically do this. Dropbox for example has it in the footer with all of its other links. The advantage of this, is that you keep potential customers more focused on whatever you're trying to focus their attention on, while keeping your customer support costs down.
