This is a question that literally nobody has ever asked me, but I'm going to answer it anyhow.
The short answer is, something cool and brutal with plenty of muscle, mysticality and moxie. You will know that a band name is metal when you hear it and have a sudden craving for beer and headbanging. However, for those whose are insufficiently TRVE I have assembled this guide of helpful hints. Endure.
1. Magic the Gathering cards often make good band names. Seriously. Ancestral Recall are so obviously a supercharged pagan-metal mob who come from the Northern lands to rape, pillage, and deplete your mead, possibly with occasionaly acoustic paeans to Odin and Thor. So are Legions of Lim-Dul although they're probably a bit more creepy and Satanic. Starstorm are a progressive band like Dream Theater though with hints of DragonForce, and Hammer of Bogardan are probably a bit like a harder edged Iron Maiden. Whereas Black Lotus are a stoner type band a bit like Acid Bath or Scissorfight. On the other hand, there's the thrashtastic Oblivion Stone and Masked Gorgon and the slightly more partyish but still thrashin' mad Skull Catapult, and the brutal, grinding death metallers Necropotence. I think you get the idea. But seriously... I know of at least two metal bands named after Magic cards. One is called Order of the Ebon Hand after the black uncommon from Fallen Empires and the other is a local band of a friend of a friend of mine. Its name? Phyrexian Warbeast. Yeah. Also, although not strictly a card but a character mentioned in many cards, see Yawgmoth from Holland.
2. So do spells from Dungeons and Dragons. Although less so. I would pay money (up to 4D6 pounds) to see bands called any of the following: Power Word: Kill, Miracle, Finger of Death, Abi Dalzim's Horrid Wilting, Ball Lightning, Creeping Doom, Bigby's Crushing Hand (who probably sound a bit like Ned's Atomic Dustbin, actually) Seven Eyes, and, of course, Fireball. Woo.
3. DO NOT give your band any name involving excreted bodily fluids unless you are grindcore. This means you, Pissing Razors, you, Soilwork, and you, Moonblood - the latter of whom, incidentally, are a trio of large, hairy, very male Germans who only release vinyl albums limited to 666 (har, har) copies. Would you go to see a band called Spunkbubble or Shitflinger at all? I think not. Bodily fluids are more the realm of punk I'm afraid.
4. Everything's better if it's of death. Though be careful not to overdo it. But seriously - Megadeth, Napalm Death, Lawnmower Deth, Stormtroopers of Death, Hospital of Death... all are ace. Even Death Panda, the alarming project of Marty Friedman formerly of Megadeth and a squadron of Japanese teenage girls (no, really, this actually exists.)
5. DO NOT try to be cleverer than you actually are. Metalheads are not hipsters. They do not like smugness and prefer iron to irony. Okay, Skyclad could get away with their pun-laden antics because they actually were good with words and had some tasty riffing. But you can tell that Modest Mouse, Cars can be Blue, Aereogramme, 27, Neon Neon and Minus the Bear are not metal. They're too... well, they all have this air of self-satisfiedness about them.
6. Nobody cares if it's yours. If your band's name has "my" in it then this is a reliable guide that it is a load of self-indulgent emo or borderline emo arse. My Chemical Romance, My Sixth Shadow, My Shameful, Bullet For My Valentine and the utterly faeculent My Ruin are all whine-and-blurt emo pap masquerading slightly as metal. Hence, keep "my" out your name. (My Dying Bride? Okay, okay, they're the exception that proves the rule.)
7. Silliness ist krieg. Do not eschew silliness but you must be so silly it's back into sensibility. Examples: Hospital of Death, Municipal Waste, Horse the Band, Lawnmower Deth, Glorious Janitors. If you have a band like this you should ideally be over the top and sing about drinking and partying and cartoon violence and video games and Saturday morning cartoons.
8. The word "the" is not your friend. I can count cool metal bands (and cool names) starting with "the" on parts of my anatomy without needing to remove my boots or my trousers. They are: The Chasm, The Meads of Asphodel, The CNK, The Berzerker, Therion (and that last one's cheating, I know).
9. Last, avoid the umlaut unless you were formed before 1985. This one's self explanatory.
Right then, I think I'm going to go off and rehearse with the other four members of Elder Dragon Beerbottle of Death. See you around!