How can we detect the existence of almost-complex structures? Any smooth $k$-manifold $M$ comes with a well-defined map $f:M\rightarrow BGL_{k}(\mathbb{R})$ (up to homotopy) classifying its tangent bundle.  Since $GL_{k}(\mathbb{R})$ deformation-retracts onto $O_k$, then $BGL_{k}(\mathbb{R})\simeq BO_k$, which is a cute way (though it's certainly overkill) of proving that every smooth manifold admits a Riemannian metric.  An almost-complex structure, on the other hand, is equivalent to a reduction of the structure group from $GL_{2n}(\mathbb{R})$ to $GL_n(\mathbb{C})$, which is the same as asking for a lift of the classifying map through $BU_n\simeq BGL_n(\mathbb{C})\rightarrow BGL_{2n}(\mathbb{R})$.

Can we detect the nonexistence of a
  lift entirely using characteristic
  classes?  If not, what else goes into the classification?

I'd imagine these don't suffice themselves.  I know that $w_{2n}(TM) \equiv_2 c_n(TM)$, so this holds in the universal case $H^\ast(BO_{2n};\mathbb{Z}/2) \rightarrow H^\ast(BU_n;\mathbb{Z}/2)$.  And certainly there are necessary conditions like $w_1(TM)=0$ (which of course just means that $TM$ is an orientable bundle, which is the same as asking that $M$ be an orientable manifold).  But I have no idea of what sufficient conditions would look like.  I've heard that this problem is indeed solved.  Maybe it takes some characteristic class & cohomology operation gymnastics, or maybe it even needs extraordinary characteristic classes.  Or maybe there's yet another ingredient in the classification?
Edit: Apparently I misquoted my source, and this is only known stably (which makes sense, in light of Joel's answer and Tom's comments on it).
 A: If $M$ is a $4$-manifold, the existence of an almost-complex structure can be often detected by using the following result due to Wu:

Theorem. A $4$-manifold $M$  admits an almost-complex structure $J$ if and only if there exists $h \in H^2(M, \mathbb{Z})$ such that $$h^2=3 \sigma(X)+2 \chi(X) \quad \textrm{and} \quad h \equiv w_2(X) \; \; \textrm{mod} \ 2. $$ In this case $h=c_1(M, J)$.

See Gompf-Stipsicz, 4-manifolds and Kirby calculus, p. 30 for more details.
A: Edit: Now updated to include reference and slightly more general result. 
Edit 2: Includes remark about integrability.
Similar to Francesco Polizzi's answer, there is the following Theorem concerning 6-manifolds.
A closed oriented 6-dimensional manifold $X$ without 2-torsion in $H^3(X,\mathbb{Z})$ admits an almost complex structure. There is a 1-1 correspondence between almost complex structures on $X$ and the integral lifts $W \in H^2(X, \mathbb{Z})$ of $w_2(X)$. The Chern classes of the almost complex structure corresponding to $W$ are given by $c_1 = W$ and $c_2 = (W^2 - p_1(X))/2$.
In fact, a necessary and sufficient condition for the existence of an almost complex structure is that $w_2(X)$ maps to zero under the Bockstein map $H^2(X,\mathbb{Z}_2) \to H^3(X,\mathbb{Z})$. 
I think the reason for results such as this and the one mentioned by Francesco is the following. To find an almost complex structure amounts to finding a section of a bundle over $X$ with fibre $F_n=SO(2n)/U(n)$. The obstructions to such a section existing lie in the homology groups $H^{k+1}(X, \pi_k(F_n))$. When $n$ is small I would guess we can compute these homotopy groups and so have a good understanding of the obstructions. For example, in the case mentioned above, n=3, $F_n = \mathbb{CP}^3$ and so the only non-trivial homotopy group which concerns us is $\pi_2 \cong \mathbb{Z}$. This is what leads to the above necessary and sufficient condition concerning 2-torsion. On the other hand when $n$ is large I don't know what $F_n$ looks like, let alone its homotopy groups...
For the proof of the above mentioned result see the article "Cubic forms and complex 3-folds" by Okonek and Van de Ven. (I highly recommend this article, it's full of interesting facts about almost complex and complex 3-folds.)
It is worth pointing out that in real dimension 6 or higher there is no known obstruction to the existence of an integrable complex structure. In other words, there is no known example of a manifold of dimension 6 or higher which has an almost complex structure, but not a genuine complex structure. By the classification of compact complex surfaces, those 4-manifolds admitting integrable complex structures are well understood.
