I think that most people have completely misunderstoodthe actual message of this quote, especially due to lack of context. As can be seen from the two excerpts that Tem42 has shown, it is his characters who say the lines. To recap, and save on scrolling:

     Have you heard of that madman who lit a lantern in the bright morning hours, ran into the market place, and cried incessantly, "I seek God! I seek God!" As many of those who do not believe in God were standing around just then, he provoked much laughter..."Wither is God," he cried. "I shall tell you. We have killed him--you and I. All of us are murderers... God is dead. God remains dead. And we have killed him...
Friedrich Nietzsche, The Gay Science (1882) section 125.
     With singing, weeping, laughing, and mumbling do I praise the God who is my God. But what dost thou bring us as a gift?"
     When Zarathustra had heard these words, he bowed to the saint and said: "What should I have to give thee! Let me rather hurry hence lest I take aught away from thee!"--And thus they parted from one another, the old man and Zarathustra, laughing like schoolboys.
     When Zarathustra was alone, however, he said to his heart: "Could it be possible! This old saint in the forest hath not yet heard of it, that God is dead!"

Friedrich Nietzsche , Thus Spake Zarathustra (1891) Part 2.

  But what is meant by Nietzsche’s use of the phrase "God is dead"? The madman in The Gay Science is first heard to shout "I seek God!" while running around in a marketplace. When he is confronted by the bemused crowds who find him, and far more importantly his questioning amusingly odd and silly, he shouts accusingly at the crowd "God is dead! We have killed him!"

This is nowhere near the same meaning as "God does not exist".

Rather, the "madman" - who is actually far saner than the crowd around him - is asking for God. He is sincerely asking (or maybe he's asking so as to make a vicious point) for ultimate meaning and Truth. But the crowd find any such questions silly and bemusing. Through their ignorance and petty-mindedness, they have dumped all such questions in the dustbin of history. To them, such questions are dead. They have annihilated all questions regarding anything higher. It's possible that this scene takes place in a marketplace on purpose - think about the obvious significance of consumerism and spirituality.

The second quote, regarding Zarathustra and the saint, is a similar message. The saint is a rather Taoist seeming guy, innocent and carefree, but also full of existential depth due to his desire to live a holy life. The giggling like schoolboys is a demonstration of the lightheartedness of true religious people. But the saint is unaware of something that Zarathustra unfortunately is. In this cynical age, such a life is seen as pointless. To the saint, at least, God is still very much alive. Note how Zarathustra avoids spreading such cynicism to the saint.

Nietzsche’s ideas were to somehow discard the damaged form of religion that he believed Christianity had become, and find some other form of morals, ethics and aesthetics that could take its place, even in such an empty, nihilistic and dumbed down age. These efforts, at which I believe he failed at, are obviously even more relevant today.