Can categorical data only take finitely or countably infinitely many values? I wonder if categorical data by definition can only take finitely or countably infinitely many values? And no more i.e. not uncountably many values? 
Related question: is the distribution of a categorical variable always a discrete distribution or a continuous distribution?     
 A: "Categorical" is not a well-defined mathematical term, so to answer this question we have to look to how this word is intended to be used.  It is employed in contrast to "ordinal," "interval," and "ratio."  One way to understand the primary distinctions is in terms of the groups of allowable re-expressions of the values.  In the case of the latter three, there is an order that must preserved, whence all re-expressions must be monotonic (order preserving).  For categorical variables, any bijection (including permutations) is ok:

Beyond that, anything goes with the nominal [categorical] scale.

(Stevens, quoted in the Wikipedia article.)
Another concept of "categorical" is that each outcome must be distinguishable from every other.  This strongly suggests that any probability measure must be totally discrete: that is, all subsets are measurable, implying that each category will have its own well-defined probability. (This is not the case for continuous distributions.)
This would seem to indicate that the number of categories should be finite or at most countable, but that is not evident in the literature.  For instance, an archetypal example of a categorical variable is a set of names.  The set of all possible names on any finite alphabet is countable but not finite.  It is therefore useful to allow countably infinite sets to be categorical.  For example, if we are studying names given to babies, it is convenient to let the sample space consist of all possible names (rather than all names that we know of).
A slightly less realistic, but still conceivable, example of a categorical variable would be one that uses real numbers for names.  In effect, such a variable would ignore all the usual mathematical structure on this set.  I don't see any problem with such a usage, but it's worth observing that the axioms of probability imply that any probability distribution valid in this context would (a) assign a non-negative value to each real number and (b) would assign a non-zero value to at most a countable infinity of the reals.
One application involving an uncountable sample space that supports categorical random variables of infinite, even uncountable, support is the study of random graphs.  To understand the rate of growth of some property of graphs, we would want to contemplate graphs on 0, 1, ..., $n$, ... nodes, so it's convenient to allow graphs to have countably many nodes.  Random variables defined on this set can have various types.  For instance, the mean vertex degree (if finite) could be considered of ratio type; the total vertex degree could be considered of ordinal type (and, therefore--by forgetting the ordering--is a nice example of a countable discrete variable).  If we also allow a graph to have arbitrarily many edges and are interested in, say, its connected components, then we would have a naturally occurring category that is uncountable (because each connected component determines the subset of nodes it contains and there are uncountably many subsets of a countable set).
To summarize, it is reasonable to allow categorical values to attain an uncountable infinity of possible values, while recognizing that at most a countable number of them could ever have positive probabilities.  This must be a discrete distribution, because all subsets are measurable, which is not the case for continuous distributions.
A: Alright, here's my attempt at an answer, from my (admittedly imperfect) understanding of your question.
"Categorical data" is something of a fuzzy and problematic term to begin with. Similar to the "I know it when I see it" definition of obscene material. There are some very clear cases of categorical data, where the values of a variable fall into a small number of clearly defined categories.
Beyond that, there be dragons.
At some point you get enough categories that your "categorical" variable could likely be treated as a continuous variable. Or alternately, using either subject matter knowledge or a description of a distribution, you can break a continuous variable up into categorical chunks and treat it as categorical.
So there's really two answers to your question:
Theory Answer: No. You could have infinitely many categories, but for some reason decide not to call it a continuous variable. If you allow for decimal-based categories of an utterly unbounded variable, there's no reason I can see it wouldn't be be uncountably infinite.
I'm not sure how often this ends up coming up. In my experience at least, fairly rarely.
Applied Answer: The cardinality of most things that would ever reasonably be called categorical data have a cardinality vastly below the cardinality of N. As noted above, there are exceptions, often subject to vague judgement calls.
A: Categorical data is discrete - otherwise it would be hard to assign categories to the data.
My take is this: the natural numbers are discrete and thus categorical. They are also ordinal and interval data, but also categorical. Since the natural numbers are countably infinite we see that there are categorical variables that can take countably infinite values. That does not mean, though, that this applies for all categorical variables.
