For the search results, you'd need to 'call' something to the page since the results are dynamically generated each time, as opposed to the category pages which are 'fixed' HTML files.

There are a variety of applications you could use for this (ideally you'd want to use SSI to insert the ad-text), try looking http://cgi.resourceindex.com/...Perl/Advertisements/ at CGI-Resources.com.

All the best
Shaun