Avoda zarah is one of the things prohibited by the Seven Noachide Laws. But what about atheism? I know that the 7 Laws are often taken to include a larger number of halachot from the Torah, so would the prohibition against avoda zarah expand to include kefira as well?
Rav Moshe Feinstein, in a t'shuva about allowing children to say a generic prayer in public school (Orach Chayim II #24), refers to the Ramba"m's statement in Mishne Torah that Adam Harishon was given 6 commandments, including belief in God. No'ach and his descendants later got one more, adding up to 7. They both conclude that not only the negative aspect of believing in God is necessary - i.e. not serving other deities - but also the positive affirmation of His creation and provenance over the world, when circumstances call for it. Rav Moshe also uses the inference from the words of Ramba"m explained in @Yishai's answer.
Given the Rambam's statement:
Anyone who accepts upon himself the fulfillment of these seven mitzvot and is precise in their observance is considered one of 'the pious among the gentiles' and will merit a share in the world to come.
This applies only when he accepts them and fulfills them because the Holy One, blessed be He, commanded them in the Torah and informed us through Moses, our teacher, that Noah's descendants had been commanded to fulfill them previously.
However, if he fulfills them out of intellectual conviction, he is not a resident alien, nor of 'the pious among the gentiles,' nor of their wise men.
It would seem that the answer is no, it is not permitted.
As far as I'm aware, just about every posek assumes that all nations are obligated to believe in God in some way or another. This is stated explicitly by Rav Shmuel ben Hofni Gaon (commentary to Beraishis 34:12), Rabbeinu Nissim Gaon (intro to Talmud), probably the opinion of the Sefer Hachinuch (commandment 417, and Minchas Chinuch there), Maharal (Gevuros Hashem ch. 66, in his comparison between murder and the denial of God), Maharatz Chajes (Kuntres Achron published in the end of Minchas Kanaos), the Chazon Ish (Y.D. 62:20), R. Yaakov Kamenetsky (Emes L'Yaakov Beraishis 8:22), R. Moshe Feinstein (O.C. II:24), R. Reuvain Margolios (Margolios Hayam Sanhedrin 56a #25) and R. Ahron Lichtenstein ("Seven Laws of Noah" pg 78).
Most of the above assume that this is the case either because there needs to be an underlying philosophy behind keeping the seven commandments (see Rambam Hil. Melachim ch. 8), as part of the prohibition of idolatry, or because it is included in the restriction against blasphemy (this is stated explicitly by R. Margolios and R. Lichtenstein).
However, there is, as far as I know, one posek who disagrees: R. Moshe Shternbach. He writes in Teshuvos Vehanhagos 3:264 and 3:317 that non-Jews are not obligated in believing in God, as this is only obligated for (and perhaps the only difference between them and) geirei toshav.
"Ben Noach" as defined by Sanhedrin 56a refers to all non-Jewish humanity, to Gentiles on a whole. The seven commandments that all Gentiles are commanded to keep are the law of judgements, and prohibitions against cursing God's name, worshipping idols, forbidden sexual partners, murder, theft and eating meat taken from an animal while it's alive. According to the Talmud, all the commandments are prohibitions, only prohibitions being counted amongst the seven except one, the law of judgments which is the only one to have an active and prohibitive quality (Sanhedrin 58b-59a).
The seven commandments concern actions that a court can judge, not beliefs. And according to the Talmud, Maimonides and Sefer haChinuch, breaking any of the seven laws brings the liability of death. Sanhedrin 57a says "their warning is the death sentence" and "a child of Noah is executed for the violation of the seven laws". Mishneh Torah, Laws of Kings and Wars, chapter 9 law 14 states that "A gentile who transgresses any one of these seven commands shall be executed." Sefer hachinuch, law/section 26, states, "And there is yet another difference – as when the nations transgress one of their [seven] commandments, they are always liable for the death penalty."
Based on the prohibitive qualities of the law against idolatry, the fact that the laws govern actions and not belief, and the fact that breaking one of the seven laws brings the liability of death in a righteous court, it is clear that belief in, acknowledgement of, fear of and recognition of God is not one of the seven laws. A person does not get the liability of death for not acknowledging the existence of God.
Therefore, atheism is permissible for Gentiles ("bnei noach).
This is not about whether it is morally important to accept the truth of God's existence. It's not about whether there may be some moral obligation (not divine obligation or seven law obligation) to know that God is. The fact is that the seven laws do not forbid atheism for Gentiles at all.
Unfortunately it is too enticing for those who know of the divine commandments for Jews to mix them up with the innately different set of divine commandments that Gentiles must keep.