Why is Khovanov homology considered a 'categorification'? I understand that the Euler characteristic of Khovanov homology is the Jones polynomial. But in what sense does this give category theory structure to the Jones polynomial, i.e., what are the objects and morphisms?
 A: The idea is that Khovanov homology is a functor out of a category of tangle cobordisms. Bar-Natan's notes are a great reference for this.
Khovanov (2002) sets this up in a "tangle 2-category:" the objects are sets of even numbers of oriented points. The 1-morphisms are planar diagrams of cobordisms between them (so that which line in a crossing is on top is important). Hence a 1-morphism is a (diagram of a) tangle, and 2-morphisms are diagrams of oriented tangle cobordisms. Khovanov constructed Khovanov homology as a 2-functor from this category to a category built out of chain complexes of abelian groups. There are subtleties to this setup, however: Jacobsson (2003) showed that it's not functorial when generalized to $\mathbb Z[c]$-modules.
However, this is not why people say Khovanov homology is the categorification of the Jones polynomial. Mike Shulman's comment is right: categorification doesn't just mean "turn things into categories," but is a vaguely defined process of adding categorical structure to things: replacing sets with vector spaces or abelian groups; functions with functors or sheaves; rings with tensor categories; and so forth. Replacing a polynomial with a bigraded abelian group fits into this paradigm, even in the absence of an explicit category or functoriality. The many answers to this question are great for explaining how to think about categorification.
