How to place ads at top of category pages?

I would like to place a relevant ad at the top of each category page on my site. In theory, you would visit the category page and there would be a banner ad and then the content or most recent posts below. Each category page would have a different ad.

Much like what is being done on this site
http://www.bestgreenblogs.com/category/editors-choice/

Alternatively, is there a way to make each sidebar for each category different (for ad placement)? I've managed to have a static home page with a separate right side bar. Then all my other pages have the same right side bar.

Thanks!
Ruth

eta: Tim from best green blogs told me that he inserts the banners on a particular template page to make them show up correctly in Wordpress. Anyone know how to do this?

I see one category template in my cpanel files. WP Codex says to change looks of each category you can make separate category template files by copying original category template. So you'd have category template a, b, c, etc. But how to make it so these new category templates show up correctly or are being called correctly in then end? If that makes any sense?