How to put stuff in Header?

I notice most WP sites have all sorts of things inside the header block. I cant even manage to get a graphic in it without it replacing the title.
I would like to put a graphic, an adsense banner, the search, and a small menu in it.

Or, is what I see on the sites not really the header but just a custom block?

Thanx
Kicker