The Stoner Witch and Stag covers are just great in their simplicity, you'd have no idea what kind of music awaits you when looking at those illustrations and you've never heard of the Melvins before. I especially like the swan on the original cover of Stoner Witch.
And yes, I agree that skulls are some of the most cliché (and thus boring) art elements you can use for a band that plays heavier music. Honestly, I don't know why they use them so much in the recent years. I didn't like the similar looking "Basses Loaded" and "A Walk with Love and Death" album covers very much because of it.
It might also all just be a little joke to make fun of heavy metal bands by using cutesy cartoon skulls in abundance, though.