Is it only performance of the covers you are interested in, or also recording the covers?
If the former, in practice I suspect most small, independent bands DON'T contact the original artist and ask permission to perform a cover of their song - unless the artist is a friend! As a case in point, my little band haven't contacted Joni Mitchell (whose songs we perform regularly). [In legal terms, as far as I understand, this is all fine because the venues in which we perform should be paying a fee to a performing rights organisation such as PRS etc.] We have, however, contacted our singer-songwriter friend to ask permission to use her songs. No money changed hands for that, and we do a bit of mutual advertising.
Recording a cover is a different matter, however, and I believe it doesn't matter whether it is a recording of a live performance or a studio recording. Legally you are required to get a license from the band whose songs you are covering. I can't vouch whether all bands follow the law, but as an example of 'what actually happens' I can tell you what my band did when we released a CD including covers of other artists' songs:
- We contacted the bands (which included successful folk artists such as Show of Hands and Tracy Grammer) whose songs we were covering, explained we would like to put our versions of their songs on a CD that we'd be selling, and asked their permission/conditions.
- Some of them sent us a standard 'Mechanical License Request Form' with a fixed royalty rate per 1000 copies of CDs produced. We paid this rate upfront.
- Some of them gave us permission to use their song for no payment, but told us how they would like to be credited.
- One artist's estate refused permission. We therefore did not record their song.
- For singer-songwriters who are our friends, we drafted a suggested Mechanical License Request Form for their agreement - to respect the fact that they too deserve to earn money from their music! We are therefore still both colleagues and friends.
So this specific example reflects both your scenarios, the no-money 'bigging up' and the 'money-changing-hands'. I have to say, though, as a small independent band we are providing only limited promotion to any successful band whose songs we cover, so it makes sense for us to pay for the privilege of using their material!