Depends on where you want your ads to appear. Post a link to your gallery for a start. Then attach a screenshot to your posting (using "additional options" when composing your message) that highlights the section where you want the ads to appear. This has indeed been asked very often already, and of course it has been answered many times over as well. There can be no generic answer as I suggested, as it depends on where you want your ads to appear. For details, you might as well search the board for the term "adsense" or "phpAds", as the threads you will get as a result would have told you what you need to do. The only difference between the method used for adsense and phpAds is that adsense just uses HTML plus JavaScript and can therefor be inserted both in themes/yourtheme/template.html as well as in themes/yourtheme/theme.php, while phpAds (which is PHP driven afaik) can only be used in themes/yourtheme/theme.php (as only that file can contain PHP code).
and after dabbling with Gallery, I realize that Coppermine is much better.
Thanks for that, but we don't see Menalto Gallery as a rival. Basically it depends on both your skill level and your intended use for the gallery application (Menalto Gallery vs. Coppermine) which one is better for you. In my opinion, this is more a matter of taste. Menalto has some features that make it unqiue as well as Coppermine. Your decision for one or the other depends on your needs.
Galley had one them that was a stripped down "bare minimum" used for integrating into other applications and I would like something like that.
There are loads of user-contributed themes. Pick one that will serve best your purpose.
I will be calling each Album into a frameset and I would like a large "leaderboard" banner ad at the top with the thumbnails below.
Using frames or iframes is not recommended at all. Frames have severe drawbacks. They should be avoided whenever possible. To be able to tell you more, a link to your gallery and your overall site would help a lot.
Joachim