Covers on an album fall under compulsory licensing in the United States, and due to the equalizing effect of the Berne Convention, probably the western world over.
There are no legal hassles involved. Unless a band changes the lyrics to the underlying work, the original artist cannot block the song from appearing as a cover on another album, hence the "compulsory" part. This is because copyright law only guarantees the author the right to exploit their work first.
Currently, statutory royalty rate in the United states is $0.091 for songs under five minutes with another $0.0175 cents for each minute over five. This is nonnegotiable (unless you the original artist wants to charge less, which generally never happens). This rate is per album shipped to retail. AIC cannot charge more than this under any circumstances. It also wouldn't cost anymore or less if Opeth decided to cover a B-side off a Dave Clarke Five single instead of a popular Alice in Chains song.