Quantum coherence is the coexistence (in a rather badly defined sense of "existence") of several non-exclusive quasi-classical descriptions of a physical system, which are all "existing" together in such a way that they produce interference effects. This makes the system behave, well, non-classically.
I don't know if the previous sentence is intuitive enough, this is after all a very technical question. Several of the words I used have a problematic or non-trivial meaning. Let me explain.
The point is that in the classical world (to be short, this is the world as seen by physics before QM, let's say the 19th century world), a physical system is a set of actual objects that have definite properties like positions and momenta. These properties have well defined values at all time, whether they manifest themselves in a measurable way or not.
In QM, it seems that when such properties are not involved in a too "intense" (again, not a well-defined concept here) interaction with the rest of the world, when they do not manifest themselves in a measurable way, we just cannot assume that they have definite values at all.
Instead, the different values a property can take kind of coexist as long as the property is not measured. This coexistence is a non-trivial mathematical relationship that allows phasing and dephasing, like in wave mechanics (hence the wave-particle duality idea). Moreover, there is still consistence in the way properties are linked together: the system (which ultimately is nothing else that the ensemble of all properties needed to describe it) does not loose its structure. But it seems that this structure is much more free to "explore" its potentialities of evolution.
This is where coherence is important for quantum computing. It is precisely because the system behaves as many different systems interfering all together that its description is in some sense similar to a parallel computation.
Decoherence can be seen as the manifestation of the rest of the world: not being isolated anymore, the quantum system loose its weird freedom, and behave like a proper disciplined classical one. No more quantum computing.
So in which sense is decoherence the "loss" of coherence? Formally, in the sense that interfering terms in the description of the system as a superposition of states vanish. What this means intuitively and physically, though, is not clear at all (that's the "measurement problem") and it is at this point that QM interpretations enter the dance. In what I wrote above I tried to give an intuitive view as free as possible from such interpretations, but I guess some of my personal views have leaked in. So take this all with a grain of salt.