So initially, some of the terms you are describing belong to modern logic, and some of the terms belong to Aristotelian logic. I will separate them to make it easier to understand.
"A logic" is sometimes used in two different ways, it can mean something like propositional logic, or it can mean a specific theory in propositional logic, which should more correctly be called "theories."
So to start with:
Propositional logic deals with entire propositions as wholes, connectives, and deductive rules.
Propositional logic deals with propositions and it has an infinite amount of variables to represent those propositions. A theory in propositional logic is a specific set of sentences in the language, meaning they use the symbols in the syntactically correct way. The initial sentences that you list are the axioms of the theory and you use the deductive rules (rules of inference) to create more sentences. Natural deduction is a specific system to apply those rules of inference in that can be applied to different logical systems.
A statement in propositional logic might look something like ((A → B) → C). A and B are propositions, they have truth values, and the arrow is the implication connective. We could decide to make a logical theory, we can call it T, that has this as an axiom. We then use the rules of inference to derive new sentences, which are called theorems. The process looks like this:
Axiom ((A → B) → C)
Theorem (A → C) HS
This is a proof of the propositional sentence (A → C) from the axiom ((A → B) → C) using the hypothetical syllogism rule of logical inference, which is what "HS" stands for.
Next we have quantifiers and predicates. Predicates allow us to break up propositions into two parts, a predicate and a subject. If we imagine the proposition W to mean "The woman is tall" then we can say that "the woman" is the subject and "is tall" is the predicate. We introduce new letters to distinguish between subjects and predicates. Capital letters are predicates and lowercase letters are subjects. The syntax is that the predicate is written before the subject, for example: "Yx". Now we have:
Propositional logic: W = "The woman is tall"
Predicate logic: Tw = "The woman is tall" where T is the predicate "is tall" and w is the subject "the woman"
Remember, propositional logic and predicate logic are two different things. You do not use predicates in propositional logic, you only deal with whole propositions themselves. Propositional logic is sometimes called "zeroth-order logic" and predicate logic is very often called "first-order logic." However, we need to introduce quantifiers to finish making first-order logic. A quantifier is a symbol that denotes the domain of discourse for whatever logical sentence you're writing. There are two quantifiers in first-order logic: the universal quantifier, ∀, and the existential quantifier, ∃. Quantifiers tell you about the variables that they "quantify over." ∀x is read "for all x" and "∃y" is read "there exists a y." An example:
∃w Tw, which says "there exists a woman who is tall", if we keep the definitions of w and T from before.
∀x∃y x+y=1, which asserts "for all x there exists a y such that x+y=1." This is true if we treat x and y as numbers and + as the addition sign (right now they're merely syntactical things with no inherent 'meaning'; model theory gives them meaning).
Again, first-order logic is the same as propositional logic in the sense that "first-order logic" refers to a specific syntactical system; a theory of first-order logic means a specific set of sentences that are axioms of your theory, rules of inference, and theorems that you derive from the axioms (if any can be derived).
What I've said so far is the modern logic of your question. The other terms refer to ancient/medieval/Aristotelian logic and I will let someone else explain them in detail, but I will give a brief overview.
Aristotle's logic is called syllogistic logic because it focuses on what are called syllogisms. This is something of the form:
Socrates is a man
All men are moral
Therefore, Socrates is mortal
Where the first two things are premises and the last is a conclusion. We used a specific syllogism as our rule of inference before, but there are many other modern rules of inference that are not syllogisms. Categorical propositions are similar to quantifiers, but remember that this is old and not modern logic. Categorical propositions are propositions that say one of these four things:
All x are y, No x are y, Some x are y, Some x are not y.
A categorical syllogism is a syllogism that uses these types of propositions as their terms; our above example with Socrates is not one because it only uses a categorical proposition once, "All men are moral," the other two propositions are not categorical because they are not an example of one of the four above definitions.
Aristotelian logic (syllogistic logic), propositional logic, and first-order logic are not the same thing. They all use deductive rules, however. Natural deduction is a specific type of deduction that is applied in theories stated in modern logical systems (zeroth, first are our examples) to derive theorems from given axioms.