an add just below the navigation bar div id="navbar" using the full width of your site you put in header.php
near the end of header.php you have something like:
<div id="navbar" class="clearfloat">
<ul id="page-bar" class="left clearfloat">
<li><a href="<?php echo get_option('home'); ?>/">Home</a></li>
<?php wp_list_pages('sort_column=menu_order&title_li='); ?>
</ul>
<?php include (TEMPLATEPATH . '/searchform.php'); ?>
</div>
********PUT YOUR ADD CODE HERE
</div>
********YOU MIGHT ALSO TRY THIS PLACE
<div id="page" class="clearfloat">
I would put the code into a new DIV, so you can give it a style in style.css, like this:
<div id="adheader-lb">
your add here, maybe an adsense link block
google_ad_width = 728;
google_ad_height = 15;
</div>
with this div id="adheader-lb" you can set some height, margin, border or background color in style.css, the following code would just center it in the width:
#adheader-lb {
margin: 0 auto;
text-align: center;
}