Perhaps I can supplement Jim's answer a little.
In the paper "Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln uber Polynomringen" Soergel shows that there are certain graded indecomposable bimodules over a polynomial ring (now known as Soergel bimodules) which categorify the Hecke algebra. (Note that these are not projective!!)
That is, the indecomposable objects are classified (up to shifts and isomorphism) by the Weyl group, and one has an isomorphism between the Hecke algebra and the split Grothendieck group of the category of Soergel bimodules.
As a consequence, one obtains a basis for the Hecke algebra which is positive in the standard basis (as follows from the construction of the isomorphism of the Grothendieck group with the Hecke algebra) and has positive structure constants (because it is a categorification).
Soergel conjectures that this basis is in fact the Kazhdan-Lusztig basis, which would imply positivity in general.
Up until now there are only two cases when one can verify Soergel's conjecture:
- when one has some sort of geometry (in which case one can show that the indecomposable Soergel bimodules are the equivariant intersection cohomology of Schubert varieties, and then use old results of Kazhdan and Lusztig). This shows Soergel's conjecture for Coxeter groups associated to Kac-Moody groups (in particular finite and affine Weyl groups).
- when the combinatorics is very simple (i.e. for dihedral groups (Soergel) or universal Coxeter groups (Fiebig, Libedinsky)).
Hence, up until now there are no examples where Soergel's conjecture has yielded positivity when it was not known by other means. Also note that in the vast majority of cases, the proof using Soergel bimodules is strictly more complicated than the geometry proof, as one needs an extra step to get from geometry to Soergel bimodules.
Soergel's conjecture would however have more far reaching consequences than a proof that Kazhdan-Lusztig polynomials have positive coefficients. For example it provides a natural "geometry" for arbitrary Coxeter groups. For example, generalising some sort of Soergel bimodules to complex reflection groups would yield a natural setting for the study of "spetses" (unipotent characters associated to complex reflection groups).
One should also note that Dyer has developed a very similar conjectural world associating commutative algebra categories to Coxeter groups. He instead considers modules over the dual nil Hecke ring (which is the analogue of the cohomology of a flag variety), and has many nice results and conjectures. (Much of his work considers more general orders than the Bruhat order, and so will probably come in handy soon ...!)
While I am at it I should mention Peter Fiebig's theory of Braden-MacPherson sheaves on moment graphs. This is (in a sense made precise in one of Peter's papers) a local version of Soergel bimodules, and hence many questions become more natural on the moment graph.
Finally, one should mention the recent work of Elias-Khovanov and Libedinsky, which give generators and relations for the monoidal category of Soergel bimodules for certain Coxeter groups. (Elias-Khovanov in type A and Libedinsky in right-angled type.) These are very interesting results, but it is unclear to what extent they can be used to attack Soergel's conjecture.