The Kazhdan-Lusztig polynomials contain all kinds of representation theoretic (and other kinds of) informations.
For example the character of a simple module over a Lie algebra with Weyl group $W$ can be read of from the KL-polynomials in the following way: $$ch(L_w)=\sum_y (-1)^{l(w)-l(y)}P_{y,w}(1) ch(M_y)$$ here $L_w$ resp. $M_w$ denote the simple resp. Verma module of highest weight $-w(\rho) -\rho$.
What are other examples of important information encoded in KL-Polynomials?
The Kazhdan-Lusztig polynomials encoded a good deal of topological information concerning Schubert varieties. For example, in
Kazhdan, David; Lusztig, George. Schubert varieties and Poincaré duality. Geometry of the Laplace operator (Proc. Sympos. Pure Math., Univ. Hawaii, Honolulu, Hawaii, 1979), pp. 185-203, Proc. Sympos. Pure Math., XXXVI, Amer. Math. Soc., Providence, R.I., 1980.
it is proved that if $W$ is a Weyl group, the coefficients of the Kazhdan-Lusztig polynomial $P_{u,v}(q)$ equal the dimension of the local intersection homology spaces of the Schubert variety $X_v$ at a point on the Schubert cell indexed by $u$.
You may want to see chapters 5 and 6 of the following book for more applications and references:
Björner, Anders; Brenti, Francesco. Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005. xiv+363 pp. ISBN: 978-3540-442387; 3-540-44238-3
It's worth keeping in mind here that the 1979 paper by Kazhdan and Lusztig dealt quite generally with Iwahori-Hecke algebras of arbitrary Coxeter groups, not just the finite Weyl groups (or even the Weyl groups attached to Kac-Moody algebras). For the finite and affine Weyl groups the connections with Schubert varieties are a major motivation for the Kazhdan-Lusztig polynomials, since the polynomials encode important geometric data as Leandro points out.
For the types of representation theory that involve Coxeter groups in the role of "Weyl groups", there tend to be good analogues of the original conjecture for finite dimensional semisimple Lie algebras and their highest weight representations of arbitrary dimension. This is certainly a major application of the ideas, since it leads to new alternating sum formulas for unknown characters, with values of the polynomials at 1 as the coefficients.
On the other hand, it's essential to build into this kind of character formula the pair of elements of the Coxeter group over which summation occurs: these are related by the Chevalley-Bruhat ordering, also a very general notion for Coxeter groups. In fact, the polynomials in isolation are not especially noteworthy. As Patrick Polo showed in type A, any non-negative polynomial with integral coefficients and constant term 1 shows up somewhere as a Kazhdan-Lusztig polynomial. (The non-negativity of coefficients is still an intriguing open conjecture from the original K-L paper, with no apparent general interpretation of the polynomials as a guide.)
I should also mention that the coefficients of the polynomials associated to a finite Weyl group determine the multiplicities of simple modules in layers of the Jantzen filtration for a Verma module, as indicated by Chuck in a wider setting. However, the proof by Beilinson-Bernstein of Jantzen's older conjecture on the filtrations shows that his conjecture is even stronger than the Kazhdan-Lusztig conjecture. (Chapter 8 of my graduate text surveys a lot of this in detail, but without being a complete treatment.)
Certain Kazhdan-Lusztig polynomials compute the so-called Brylinski-Kostant filtration on weight spaces of irreducible representations. They also compute multiplicities of irreducible modules occurring in global sections of line bundles on cotangent bundles of flag varieties. These two ideas are related.
In more detail: Let $G$ be a semisimple algebraic group over $\mathbb C$. Fix a Borel subgroup $B \subseteq G$ with unipotent radical $U$ and choose a principal nilpotent element $X \in \textrm{Lie}(U)$ (a principal nilpotent element is one whose $G$-orbit is dense in the subvariety of all nilpotent elements). Let $\lambda, \mu$ be dominant weights and consider the $\mu$-weight space $V_\mu(\lambda)$ of the irreducible representation $V(\lambda)$ of $G$. Then there is a filtration -- the Brylinski-Kostant filtration -- on $V_\mu(\lambda)$ coming from the action of $X$ on $V(\lambda)$: define $ \mathcal F^n( V_\mu(\lambda) ) $ to be the subspace of $ V_\mu(\lambda) $ consisting of vectors killed by n+1 applications of $X$. Since $X$ is nilpotent, this does indeed give a filtration on $V_\mu(\lambda)$.
Now, an important theorem due to R. Brylinski (1) is that certain Kazhdan-Lusztig polynomials give the dimensions of the subspaces in this filtration. This is a very interesting theorem: to prove it, Brylinski actually proves an intermediate geometric theorem relating Kazhdan-Lusztig polynomials to twisted functions on G/T (which are connected to degrees of sections of line bundles on the cotangent bundle of G/B), so that along the way she gives yet another interpretation of Kazhdan-Lusztig polynomials. In particular, they compute multiplicities of irreducible modules occurring in global sections of line bundles on the cotangent bundle of G/B. They also give information on the degrees of sections of these bundles (I will just refer to Brylinski's paper for the appropriate definition of "degree").
Here I will humbly submit my own work: in (2) I extended some of Brylinski's results to the case where the nilpotent element is not necessarily principal. In this case, certain Kazhdan-Lusztig polynomials also appear in an analogous filtration. Further, the full cotangent bundle of G/B is replaced by an appropriate subbundle E of the cotangent bundle, and one has the following result: certain Kazhdan-Lusztig polynomials compute multiplicities of irreducibles occurring in global sections of line bundles on E. (Unfortunately the full general statement that one would like to make is still a conjecture, due to difficult technical issues involving cohomology vanishing of these bundles).
Remark: Both Brylinskis have made fundamental contributions to the theory of Kazhdan-Lusztig polynomials. Jean-Luc Brylinski and M. Kashiwara, and independently Beilinson and Bernstein, proved the Kazhdan-Lusztig conjectures (this is the interpretation mentioned by Jan in his question); Ranee Brylinski, Jean-Luc's wife, gave the interpretation I've described above.
References:
(1) Brylinski, R. K. Limits of weight spaces, Lusztig's $q$-analogs, and fiberings of adjoint orbits. J. Amer. Math. Soc., 1989, Vol. 3, pp. 517--533.
(2) Available on the ArXiV here.
I'm not sure whether this would be considered an answer but there is a "concrete" interpretation of the coefficients given in http://arxiv.org/abs/1212.0791 .