If you never used Mod_Rewrite then you are opening a whole new can of worms. You will need to know how to write regular expressions. You did a search on mod_rewrite and came up with nothing....impossible! There is tons of information on mod_rewrite (Apache)....have you tried Google. That's assuming you have Apache. If you are using Windows IIS then you will need something like ISAPI Rewrite. Regular expressions isn't too bad, once you have it setup and stable you are in good shape, but any drastic site changes in the future may also effect the rewrite code and the expressions will need to be rewritten or more lines added.
Did anyone happen to think of the easy way to do this? Well, here is the ultimate solution: If your website is hosted on IIS, contact the server administrator and have them set up a server wide header or footer. Doing this will automatically put a header or footer on every page and you won't have to open a single one. I am not exactly sure how to do this with Apache, but I believe it is possible using some Add-Handler script of a sort. Sure, it requires root access on the server - meaning the Admin would have to do it, but it is really not that big of a deal. If your admin can't do it, then you could host your site at www.kasl.info - they would do it.
Why not just make a php administrative website accessing a mysql database to store advertisements, than make a strip of code that will read from it and put it in each page. If they're in HTML, you could just put the PHP code between <? and ?> than change the name to *.php, why don't you just do that? Or simply use Java to make it randomly pick banners.