In this article I will start by disussing a particular grammatic element in Arabic. I need to start with a general discussion, so you will understand when I move to its applicability to Arabic onomastics.
In Arabic, there is a bit of grammar called iḍāfa and usually called "the construct state" in English; no, I have no idea why "construct state".
Iḍāfa consists of putting two nouns next to each other, in order to show possesion and similar relationships.
I must start with some explanations. In Arabic, all nouns are innately either definite or indefinite; this is the difference between the something (definite) and a something (indefinite). Note that all Arabic adjectives are innately indefinite, and that an adjective must agree with its noun as to being definite or indefinite. Any indefinite noun, and all adjectives, can be made definite by adding the prefix al-. Oh, and in Arabic, personal possessive pronouns (mine, hers, ours, etc.) are suffixes.
In iḍāfa, the first noun cannot have the prefix al- added, nor any personal possessive pronoun suffix. As well, the first noun determines the case of the phrase (nominative, genitive, or accusitive). The second term may or may not have al- added. The phrase as a whole is definite or indefinite depending on the second noun; note that some nouns are innately definite, and if such a noun is the second term, the phrase will be definite. Further, the second term is always in the genitive.
However, when discussing names we are only concerned with the nominative case; I only mentioned cases in order to be complete. You can now go ahead and ignore cases.
Adjectives, even those formed from place-names, act differently, in that they must be definite or indefinite according to the noun they modify (as I mentioned before). This is true even though (some) Arab grammarists say noun-adjective phrases are also iḍāfa. That may or may not be true, but it's confusing as hell to amateur onomasts, so ignore it; treat noun-adjective phrases as their own thing, separate from iḍāfa.
Here are some examples; Aḥmad, as it points to a particular person, is an innately definite noun (even though there are many people named Aḥmad, any personal name is definite), and does not need al- to make it definite; kātib, secretary, is indefinite. If we want to say "Aḥmad's secretary" (IOW, "The secretary of Aḥmad"), kātib would be have to be left indefinite because it's the first word. So "Aḥmad's secretary" is kātib Aḥmad. However, if a perfume maker, ʻaṭṭār (which is innately indefinite), had a secretary, that would be kātib ʻaṭṭār or kātib al-ʻaṭṭār, depending on whether you wanted an indefinite or a definite phrase (the second literally means "(the) secretary of the perfumer").
You will notice the "possessed" comes first, then the "possessor". For instance, the city too often mis-romanized as "Medina" is Madīnaẗ al-Nabi, "major-trading-center/city of the Prophet."
So, why did I put "possessed" and "possessor" in quotation marks? Because, while iḍāfa is usually used in a owned/owner situation, there are times it is used for other relationships. For example, in the case of containers, the first word is the container and the second the thing contained. For example, ṣundūq is "a box" and matar is "rain", so ṣundūq mater is "a box of rain." Iḍāfa is also used to indicate the material a thing is made of; the first word is the thing, the second the material. It can even refer to a purpose and the thing that does that purpose.
So, what of onomastics?
As an onomast, you will be concerned with possessed/possesor, not the other uses of Iḍāfa - - - and much more often with noun-adjective combinations.
You see, in a name like Muḥammad al-Baghdādī, the al-Baghdādī part is the definite form of an adjective. Baghdād is a city, the corresponding adjective (Baghdadian/Baghdad-like/having-to-do-with-Baghdad) is Baghdādī; since you want to modify the definite Muḥammad you must use the definite form, al-Baghdādī. Similarly for al-Dimashqī, al-Khurasānī, al-Maghribī, etc.
As for iḍāfa itself...
It shows up in name phrases such as ibn Yaḥyā; this is literally "son Yaḥyī". However, this is in iḍāfa format, so the meaning is "son (possessed) Yaḥyā (possessor)" or, "son of Yaḥyā." Kunyas are also in iḍāfa, with Abū or Umm being the "possessed" and the name of the child being the "possesser"; Abū Fātik is not "Father Fātik" but "father of Fātik" (Or "Fātik's father").
Also note that in a name phrase such as ibn al-Naṣr, al-Naṣr, though an adjective made definite (the victorious) is not, in fact, modifying ibn; this person is the son of someone usually called "al-Naṣr," rather than called by his ism, and al-Naṣr is being used as if it were a definite noun. So again, the meaning is "son (possessed) al-Naṣr (possessor)" or, "son of al-Naṣr"---not "the victorious son."
And that concludes the discussion of Iḍāfa and noun-adjective phrases, of the sort an amateur onomast is likely to come across. I hope this has helped!