Well the "new world" was discovered when Muslim mariners from Al-Andalus were caught in a storm and ended up in the Caribbean. Fortunately the natives on the island they landed on were friendly, and when the mariners returned two years later an expedition set out along with missionaries. In the 12th-13th centuries (by Christian reckoning) even when knowledge of this "new world" filtered across the Muslim-Christian divide in Southern France, none of the polities of the Christian world had the resources or desires to move west. The Muslims moved north along the North American coast slowly, as well as west to Central America, and then south. Between Jihad and missionaries, the bulk of the native population converted and became assimilated, and the Muslim light cavalry was especially effective in many regions.
The northern islands in the Atlantic (OTL Greenland, Iceland) were settled by Christians, and north of the great inland sea (Great Lakes) with a line to the Atlantic from the great falls (Niagra) you have a Christian majority country as the weather and (at the time) lack of gold or attractive agricultural resources) were less attractive to the Muslims. If you draw a line from the western edge of the great inland sea (OTL Duluth) to the western ocean this is the divide between Muslim America and Christian Borea, in the east go from the great falls to the line of the north-south river on to the large lake (Hudson/Lake George), east and north of this line is part of Borea, the north-south river divides Borea and America, with the islands in the harbor being Borea mostly, except the largest one (OTL Staten island) being American and after many conflicts by treaty all harbor islands and the western end of the long island are demilitarized.
The largest population of non-Muslims in America are the Jews, who fled the persecution in the Christian lands and were offered transport to America and exempted from the Jizya if they went to America, if they stayed in "eastern" Muslim land the Jizya remained in effect. Very few Christians live in American states - in most Christian immigration was forbidden or strictly limited until recently and restrictions like the Kizya remain in force. In Borea the population is almost 100% Christian, as restrictions on immigration of Jews and Muslims were severe until very recently, and even now they are second class citizens. A few Eskimo keep to tribal religions, but they are the ones furthest from civilization.
Of course exact situations vary widely in the western world. The unity of Muslim rule in the Americas broke up long ago, and there are numerous Muslim states from the southern trip of America to the Borea border. Also the divides in Islam, Shi'a/Sunni and others are reflected in various American entities. Likewise Borea is not unified, and there is some variation among them and while east of the Stone Mountains (OTL Rockies) the Christians are Catholic rite, west of those mountains settlers are mostly Orthodox having come from the lands of Rus.
In order to have America not be Muslim majority you need to have the Christians discover the "new world" first and have the Muslims either uninterested in settlement or somehow militarily inferior. I don't see any states in the "new world" that are not overwhelmingly Christian or Muslim majority, as neither will be willing to see power sharing in the new territories - one or the other will become supreme in any given territory, and the minority will be marginalized at best, expelled or forcibly converted at worst.