It was thought, by Frege and Pierce the (so-called forefathers of modern formal logic), that statements (or what they and some modern mathematicians would have called propositions) could be classified by their form using notation. Furthermore, they wished to use that notation to connect the form of a statement with its use in an argument.
The analysis of statements into a form containing a subject and predicate is just about as old as Logic itself, leading all the way back to Aristotle. The use of notation to systematically record statements about mathematics is most frequently credited to George Boole's An Investigation of the Laws of Thought and De Morgan's works (though it is possible that Leibniz also produced similar work nearly 200 years prior to both Boole and De Morgan, most strongly asserted by Russell in History of Western Philosophy. What is certain is that Leibniz clearly identified principles of logic needed to analyze mathematical statements using notation).
The use of notation to record statements about mathematics into a subject-predicate form is most frequently credited to both Frege and Pierce independently. We know of Frege's development primarily because of Russell's subsequent work with Whitehead on an argument that mathematics is a part of logic (the most rigorous presentation of which can be found in their Principia Mathematica).
The term "predicate logic" as well as the term "predicate" have many different meanings depending on the context in which they are being used. Predicate logic, in its widest sense, simply refers to any logic which supposes that statements can be analyzed into a predicate subject form where the predicate is often assumed to assert its subject has a certain property (and that the subjects are to come from a collection over which the predicate has a well defined "meaning").
It is important to note that predicate logic's origins are deeply intertwined with the origins of the notion of set (or class, or collection). For this reason it can be difficult for modern mathematicians to appreciate that prior to the efforts of Skölem to base set theory on first-order logic, predicate logic sometimes referred to a semantic theory, sometimes a syntactic theory, sometimes a vague combination of syntax and semantics all of which were sometimes first-order, sometimes second-order, and sometimes something quite different. (a more detailed history of the development of first-order predicate logic can be found in Gregory H. Moore's The Emergence of First-Order Logic.)
Modern mathematicians often use predicate logic to refer to any of a number of equivalent Hilbert-like formalisms which include the axioms of a formalized sentence (propositional) logic together with axioms containing implications of quantified sentences (e.g. $P(x) \rightarrow (\exists y)P(y)$ and $(\forall x)P(x) \rightarrow P(y)$) and inference rules containing implications of quantified sentences. The use of the term "predicate logic" to refer to a semantic theory is almost entirely a thing of the past, as we now use the term "Model Theory".
A "predicate" in modern model theory is defined from a preconception of set, collection, or "domain" of "individuals". A predicate over a domain of individuals is an assignment of a truth value (truthhood or falsehood in classical model theory) to the individuals of a domain. A predicate of $n$ arguments is an assignment of a truth value to each ordered set (ordered $n$-tuple) of individuals from the domain.
The tricky thing about this commonly accepted definition is that when the domain is "infinite" it is no longer easy to say just how the word "predicate" is to be defined, for one can not simply construct a truth table for all predicates as is possible when the domain is finite i.e. the very notion of "predicate" in model theory is (carelessly) accepted in this vague form (hence your confusion, and that of many working mathematicians, over the distinction between the "similar" notions of predicate, functions, class, set, etc.) This confusion is the residue of predicate logic's still developing past.
Universality and existence are introduced into Model Theory as extreme forms of assignment of a truth value to individuals or tuples of individuals: a predicate which assigns the value of true irregardless of which individual from the domain is its argument is said to be true for all individuals of the domain (universal), and a predicate which assigns a value of true to at least one individual of its domain is said to be true for some individuals of the domain (existential). Alternatively, a notation is used (in the model theory, which should be odd to a "pure" model theorist) to stand for these kinds of predicates: $(\forall x)P(x)$ is read as "for all ex capital pee of ex" and asserts (in model theory) that the predicate $P(x)$ is true for any argument which is an individual in the domain, $(\exists x)P(x)$ is read "there exists an ex such that capital pee of ex" and asserts that the predicate $P(x)$ is true for at least one argument which is an individual in the domain.
Note, the term "predicate" is often replaced with the term "relation" though, as previously mentioned, there continues to be a great deal of confusion amongst working mathematicians as to what they actually "mean" by these terms outside of a preconception of set theory (in fact some mathematicians are unable to say just what "relation" or "predicate" or "function" might mean outside of a theory of sets).
Note, as well, universality and existence are but two possible forms of assignment of truth values to individuals in a domain by a predicate.
Finally, the most clear and exact description of predicate is to be found in a formal language the most common of which is a Hilbert type formalism where the word "predicate" is used as a classification word for signs (symbols) used according to specific rules of the formal language.