What are some examples of interesting uses of the theory of combinatorial species? This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer.
I've often heard it claimed that combinatorial species are wonderful and prove that category theory is also useful for combinatorics. I'd like to be talked out of my skepticism!
I haven't read Joyal's original 82-page paper on the subject, but browsing a couple of books hasn't helped me see what I'm missing. The Wikipedia page, which is surely an unfair gauge of the theory's depth and uses, reinforces my skepticism more than anything.
As a first step in my increasing appreciation of categorical ideas in fields familiar to me (logic may be next), I'd like to hear about some uses of combinatorial species to prove things in combinatorics.
I'm looking for examples where there is a clear advantage to their use. To someone whose mother tongue is not category theory, it is not helpful to just say that "combinatorial structures are functors, because permuting the elements of a set A gives a permutation of the partial orders on A". This is like expecting baseball analogies to increase a brazilian guy's understanding of soccer. In fact, if randomly asked on the street, I would sooner use combinatorial reasoning to understand finite categories than use categories of finite sets to understand combinatorics.
Added for clarification: In my (limited) reading of combinatorial species, there is quite a lot going on there that is combinatorial. The point of my question is to understand how the categorical part is helping.
 A: Before I learned about species I didn't understand why you sometimes use exponential generating functions and sometimes ordinary ones.  Now I understand: for species you should use exponential generating functions!
A: First of all I need to say that I know nothing about the achievements of category theory.  So far, I couldn't get myself to discover any theorem, that proves something in, say, combinatorics, using category theory in an essential way.  (Hints were given in some answers to this question, but I didn't have time to follow them yet.)
Furthermore, I have to admit that I don't know enough of the history, so I cannot claim that the following items are really achievements of a "categorical" point of view on combinatorial objects.  One may argue that one doesn't need categorical language to phrase these concepts, and it seems to me that Bergeron, Labelle and Leroux have consciously avoided it.  However, I think the "origin" of the ideas is of "categorical" spirit.
1) I'd say that the concept of equality of ordinary species, and, related to that, their molecular decomposition is something very important for it's own right, simply because it's beautiful.  I'm not sure whether this concept has been fully exploited yet in a practical sense.  Possibly it's hard to exploit because very often we encounter structures which are really unlabelled.  I read about the desire to classify objects counted by the Catalan numbers every so often: there is little to be done with species, because their defining equation is algebraic.  (I guess this doesn't preclude the existence of an interesting labelled object with isomorphism types being counted by the Catalan numbers, if you know of one, please share!)
2) tightly connected with the previous item is the very structured way to go about counting under group action.  Nils de Bruijn wrote "this kind of enumeration theory is a matter of exposition and organisation of things which are in essence trivial".  Here I think that in many cases, especially multivariate species are just the right tool.  A concrete example: "how many possibilities are there to put two red, two blue and four green balls into a round and three square boxes?"  Yes, it is easy to that, but with species it is trivial: we want the coefficient of $[R^2B^2G^4]$ in the isomorphism type series corresponding to $E_1(E(R+B+G)) E_3(E(R+B+G))$.  Again: I would like to emphasise that species give the problem structure, and it would seem to me that this is at the heart of "categorical thinking", even if no category theory is involved.
3) there is at least one useful operation on species, which comes about very naturally, namely functorial composition.
4) this item is rather a question than an answer: operads have already been mentioned, does somebody know what Monoidal functors, species and Hopf algebras by Marcelo Aguiar and Swapneel Mahajan is about?  Maybe that would "really" answer the original question...
A: One further line of response would again invoke Rota:

"What can you prove with exterior
  algebra that you cannot prove without
  it?" Whenever you hear this question
  raised about some new piece of
  mathematics, be assured that you are
  likely to be in the presence of
  something important. In my time, I
  have heard it repeated for random
  variables, Laurent Schwartz' theory of
  distributions, ideles and
  Grothendieck's schemes, to mention
  only a few. A proper retort might be:
  "You are right. There is nothing in
  yesterday's mathematics that could not
  also be proved without it. Exterior
  algebra is not meant to prove old
  facts, it is meant to disclose a new
  world. Disclosing new worlds is as
  worthwhile a mathematical enterprise
  as proving old conjectures.
  (Indiscrete thoughts, p.48,
  Birkhauser, 1997).

For a couple of new worlds made possible by the species concept see:
1) M. Fiore, N. Gambino, M. Hyland and G. Winskel. The cartesian closed bicategory of generalised species of structures. Journal of the London Mathematical Society, 77(2) (2008), 203-220.
2) J. Baez et al. on stuff types (note, they call species 'structure types').
A: To see a specific example of species applied to a fairly difficult enumeration problem (counting bipartite blocks), see my paper with Andrew Gainer-Dewar, Enumeration of Bipartite Graphs and Bipartite Blocks, Electronic Journal of Combinatorics, Volume 21, Issue 2 (2014) Paper #P2.40. If you're really serious you might compare our approach to counting bipartite graphs with Hanlon's.
A: Let's start from the beginning.  The main textbook on species is this one by Bergeron, Labelle,  and Leroux, all major experts in the field.  Even if you don't want to read the book, read the introduction by G.-C. Rota (which is interesting, enlightening and relatively short.  In there, Rota writes:

"I dare make a prediction on the future acceptance of this book. At first, the old fogies will pretend the book does not exist. This pretense will last until sufficiently many younger combinatorialists publish papers in which interesting problems are solved using the theory of species. Eventually, a major problem will be solved in the language of species, and from that time on everyone will have to take notice."

It has been 13 years since these words had been written (almost to the day), so it is perhaps time to revisit this prediction.  The "major problem" part clearly did not work out.  One can argue that it's too soon to judge.  Maybe.  Maybe not.  The first part, on "sufficiently many younger combinatorialists", is more interesting and probably arguable.  There are sufficiently many people using and referencing the book - it has over 300 citations on GoogleScholar.  And if you look at these citations, it becomes clear that the book has an extended influence over a large range of fields - the language and philosophy of species are clearly useful.  
On the other hand, in comparison with the "competition", the theory of species is clearly not doing so well.  Goulden & Jackson's "Combinatorial Enumeration" and Stanley's "Enumerative Combinatorics" have been cited about 1,000 times each (yes, both are older, but still).  If you go a bit further away from the field, Alon & Spencer's "Probabilistic Method" has been cited over 3,000 times...  
My conclusions: the answer to your question is both Yes and No.  The theory of species is clearly useful, but more like a good language to use, or a guiding principle of which roads to take and which to stay clear of.  When it comes to explicitly stated "practical" problems, people seem to prefer more directly applicable tools.  I would compare this phenomenon to the influence of complexity theory on enumerative combinatorics:  whatever you are enumerating, even if your problems are non-algorithmic and in a very classical combinatorial setting, it is still useful to know what is #P-completeness, simply because this gives you a different point of view on the objects you are enumerating, and sometimes it can also save you a bit of time by suggesting that the problem might be too general and thus have no explicit solution.  
A: Composition of species is closely related to the composition of symmetric collections of vector spaces ("S-modules"), which is a remarkable example of a monoidal category everyone who had ever encountered operads necessarily used. Applying ideas coming from this monoidal category interpretation has various consequences for combinatorics as well. For example, look at papers of Bruno Vallette on partition posets (here and here): I believe that already the description of the $S_n$ action on the top homology of the usual partition lattice was hard to explain from the combinatorics point of view - and for many other lattices would be impossible without the Koszul duality viewpoint. 
A: Since the Theory of species is also about relabeling, and relabellings form permutation groups, the Theory of Species is very close related to Permutation Groups theory. Is the theory of species a part of group theory ? NO. And if it were, someone should take it out of there and make it a standalone theory. 
Imagine that someone wants to write a book containing equations like Part = E(E+), or that amazing Joyal' spines on Cayley formula. Then the author must write a lot of permutations stuff, leaving the formulas for the last chapter maybe, and confusing the reader: Is this book about permutations or about something else ?
The functorial definition avoid all the permutation trouble that would have been involved, including the definition of species on empty sets or the notion of copies of the empty set. A simple object like an empty box is not likely described by the mathematical empty set. Anyway, if there are still troubles with the empty sets and the void permutations, these are less visible in cats language. 
Hence I think the main worry of the authors was to not reload the permutation group theory - and this is highly understandable. All the pieces of this mega combinatorial puzzle were already know : Burnside rings, wreath product, the fix of an element, Polya's polynomials on symmetries and the exponential generating functions. I also think that any presentation of Species should emphasize somehow the magic of egf calculus, that is for Combinatorics what the O and 1 calculus is for the true and false Logic. 
Today, when many e.g.f.'s are listed, anyone could observe some "mysterious" relationships between egf's and it could build at least some mnemonic meanings that bring some orders in huge lists formulas. The Theory of Species tries to give  a scientific base to this collection of mnemonic meanings. It is like someone invents the classical synthetic geometry after two thousands years of analytic Cartesian geometry and he try to well found it. 
Bibliography http://www.math.sinica.edu.tw/www/file_upload/mayeh/1989Therelationsbetweenpermutation.pdf Labelle and Yeh in 1987 on Permutation groups and Species 
to all Species fans as I am -> I am also watching the talk page on wikipedia http://en.wikipedia.org/wiki/Talk:Combinatorial_species
A: Pietro, if you haven't done so by now, you really, really ought to read Joyal's paper. (I can't understand why you would express skepticism before you'd even looked at the primary sources!) 
If there is a single application of species to be singled out from this wonderful article, it is Joyal's proof of Cayley's theorem. (This proof was highlighted in Proofs from THE BOOK.) But this is only one of the treasures in the paper that await those who take the trouble to read it. 
Much of the art of combinatorial thinking (at least in enumerative combinatorics) is knowing how to draw the correct pictures, and the theory of species can be seen as a step toward turning that art into a science, by formalizing directly the operations on structures which are implicitly coded by generating function techniques. In different words, the basic functional operations on exponential generating functions are lifted to functorial operations on species. At some level such insights must have been known to combinatorialists, but the theory of species serves to formalize them in the light of day, and no less a combinatorialist than Zeilberger has found species a significant source of inspiration. 
A: The categorical perspective tells you why egf's have $n!$s in the denominator!  A species can be thought of as describing a "graded groupoid," where the grade of degree $n$ is the groupoid consisting of the action of $S_n$ on the corresponding sets.  The groupoid cardinality of a finite group $G$ acting on a finite set $X$ is just $\frac{|X|}{|G|}$, so the "graded groupoid cardinality" of a species is precisely its egf. 
In cases like the Catalan numbers where the natural generating function is ordinary, what happens is that the action of $S_n$ is free.  For example, the species corresponding to Catalan numbers really corresponds to labeled rooted binary trees, and $S_n$ acts on the labels.  The resulting quotient counts unlabeled rooted binary trees, so the generating function appears ordinary.
