"the killing of a god" or "one who kills a god" from Latin deus "god" + -cida "cutter, killer, slayer,".
Although this term wouldn't make sense to a Jew or Muslim, who believe only in an uncreated and thus unkillable God, it does for a Christian, who believe that God has a created aspect in the form of a human: Jesus Christ. Although this aspect of God is considered 100% divine, he is also 100% human, and thus capable of being killed. The term came about in reference to this man-god's death by crucifixion.
As a death metal band name, the term takes on different dimensions. It could have a Nietzschean aspect, referring to the obsolescence of values typically associated with the concept of God, or even further, the death of all absolutist thinking, effectively killing God. Thus, 'deicide' signifies the death of all the corrupted 'truths', providing fertile nihilistic grounding for the creation of new, more realistic values. This nihilism is reflected in the band's sound (on the first two albums), which defies all traditional musical conventions, opting for chromaticism in lieu of pleasing but hollow diatonic melodies.
Another possible dimension, related but distinct from the previous, is an avowal to comic book styled blasphemy. According to many if not most religious faiths, God is the source of all that is good in the world. Were the impossible made possible and God was literally killed, evil would reign supreme and the world would be under Satan's dominion (To some living in modern society, this might be preferable to the current situation). Thus, 'deicide' is the ultimate profanation of all that is considered holy, and by extension, the ultimate iconoclasm.