As an enthusiast of middle eastern (and things derived from it), I usually enjoyed naming my colonies.
If i'm colonizing as Andalusia i go with the boring Gharnatah al jadida (i think the name is even suggested by the game), for Brazil, since it's the first region you colonize, and Iberians are still influencing this society soon to be back completely on moorish control, and Iberians like to name stuff after older stuff. Otherwise, Brazil could be a relevant destination for culture exchange between east africa sailors, and maghrebi sailors. Maybe something combining both of those origins for major port names. The actual colony though, could go with the IRL "the red land" but in arabic
For the rest, though, I like to name Peru after the Andes somehow, like Jabal something, maybe an explorer or general's name, as was with Jabal Tar'iq.
Argentine I would imagine can be compared to mesopotamia, because of the big ol plata basin.
Texas and the south, could be somewhat analogous to the levant and egypt, with the mississippi being the nile, and even some nearby iskandariyyah for posterity.
East america, no doubt something with Sharqiyah in it. Maybe splice a couple european-derived names schemes since they'd be passing by to make commerce in major ports.
Mexico has the gold that makes it stand out, but also the Nahuatl speakers, i would imagine an arabization of some Nahuatl words and regions that happen to be more relevant for my colony.
The caribbean, i usually name them after sugar. Islands of sugar, or the islands of whomever is your favorite 666 ruler.
West america no doubt something with Gharbi in it. Maybe san diego becomes the Tunis/Rabat of the new world
Canada, could play along something silly like "iceland" but in arabic, since they didn't have contact with regions that cold.
Australia and new zealand could be also named after someone in particular, or since australia is a big desert filled with natives that can withstand its climate, draw a parallel to the bedouins and make it a mythical land of some djinns, the type of which we don't get back in the arabian desert.
