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?

9$\begingroup$ Categorification is not really meant in that sense. Rather it means that while the Jones polynomial is an element of a set, namely the set of polynomials, the Khovanov homology is an object of a category, namely the category of graded abelian groups (or, better, some derived category of chain complexes). $\endgroup$ – Mike Shulman Jun 18 '17 at 14:48
The idea is that Khovanov homology is a functor out of a category of tangle cobordisms. BarNatan's notes are a great reference for this.
Khovanov (2002) sets this up in a "tangle 2category:" the objects are sets of even numbers of oriented points. The 1morphisms are planar diagrams of cobordisms between them (so that which line in a crossing is on top is important). Hence a 1morphism is a (diagram of a) tangle, and 2morphisms are diagrams of oriented tangle cobordisms. Khovanov constructed Khovanov homology as a 2functor 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.

1$\begingroup$ A comment on the Jacobsson paper, since this was something that puzzled me for a while: Dror's notes (specifically problem 11.3) provide great motivation for Jacobsson's result, which is unfortunately written up only as the details of a calculation and gives little intuition. $\endgroup$ – dvitek Jun 19 '17 at 9:14