In traditional logic (that is, the tradition that started with Aristotle), a categorical proposition is one that affirms or denies a predicate of a subject. That is, a categorical proposition says "A is B" or "A is not B". For example, "Emily is happy" or "American foreign policy in the 21st century doesn't have a clear objective." That's as simple a proposition as you can get.
A hypothetical proposition is one that says that if some condition is true, then some proposition is true. For example, "If the printing press is working again, then Emily is (probably) happy."
When people use the term loosely, to say that a proposition is categorically true or that they are making a categorical statement, they mean that the proposition is true without additional conditions, especially unstated conditions. That is, they mean that the proposition is categorical, not hypothetical. But they mean it in a stronger sense than what is used in logic. They mean that there is no need to entertain doubts, qualifiers, conditions, ifs, ands, buts, etc.--because the statement says it all, end of story.
The connection with category is more obscure. Aristotle used the term "category" to mean what today we would call a predicate: that is, something that you can say about something else. For example, the predicate in "Emily is happy" is "happy". Aristotle famously tried to organize all predicates into ten fundamental kinds, called "the ten categories" or simply "the categories". Today, we still use "category" to mean predicate, but the emphasis is on grouping things that share a common predicate. For example, you might put Emily into the category of happy people. Really, that means the same as "Emily is happy", but it encourages you to think in terms of groups: happy people and unhappy people. Or you might define a category for purposes of grouping: "All people whose names start with A through E, please wait in this line; etc."
As Brian Hitchcock noted, sometimes people say "categorical" to mean a universal proposition with no exceptions. In fact, categorical propositions don't have to be universal; they can refer to just some of something or just one thing: "All women are happy", "Most women are happy", "Some women are happy", "Hardly any women are happy", and "Emily is happy" are all categorical propositions, differing by what logicians call "quantity". The first one is called "universal", the last one "singular", and the others "particular" (since they refer to part of the subject being talked about).
The usage of categorical to mean "universal" is understandable because there's a connection between universality and lacking conditions, but people who know the connection between "category" and "categorical" consider that usage a solecism. A statement about just one person or thing can still be "categorical" in the informal sense of "this is the full statement, no additional conditions needed". For example, "The Harbaugh report is categorically not true!" doesn't mean anything about lacking exceptions. It means that Jim Harbaugh will still be the head coach of the 49ers next season, regardless of people's doubts about or dislike of Harbaugh.
Most people today don't know the distinction between categorical and hypothetical. People who know what categorical means usually don't use it in the sense you found in the dictionary, meaning "unconditional", "explicit", "without exceptions", etc. A sentence like "Are you stating that categorically?" comes across as trying to use a big word without knowing what it means. Categorical is logic jargon, to be used precisely. When people use it loosely, usually they're trying to bully someone into backing down by sounding like they're speaking very precisely and formally when really they're just putting on airs. A similar abuse of logic jargon is the use of ad hominem to mean an insult.
Note that "predicate" above means the sense appropriate for logic, not for grammar, although the two are closely related, of course.