Consider a horse. We can have a complete concept of what a horse is — its definition, its essential properties — without this concept telling us whether any horse actually exists. The concept "horse" is neutral with respect to existence: it neither implies existence nor implies non-existence. Existence is added to the essence as something extra, something that comes from outside the essence itself. This is what Avicenna means by saying that in contingent beings, existence is "accidental" to essence — not that it is trivial or easily lost, but that it is not analytically contained in what the thing is.
The Necessary Existent is the one being for which the essence/existence distinction does not hold. God's essence simply is existence — or, more precisely, God is pure existence without any essence distinct from it. This is why God cannot not exist: unlike the horse, whose existence is added from outside, God's existence is not derived from anything outside. The simplicity of the divine nature follows immediately: if God had an essence distinct from existence, God would be a composite being dependent on something that combined these two aspects, which is impossible for the necessarily existent.
The question of whether the distinction between essence and existence is a merely conceptual distinction or a real distinction in things — whether there is literally something in the horse that is its horseness and something else that is its existing — became one of the most debated questions in medieval philosophy. Aquinas held that there is a real distinction in creatures (though not in God); Scotus held that there is a "formal" distinction; the Scotist and Thomist schools argued about this for centuries. The debate goes to the heart of what kind of being a creature is and how it depends on God — and it all began with Avicenna's original formulation in the Book of Healing.
The essence/existence distinction is developed in the Ilahiyyat of the Book of Healing, particularly in Book I, chapter 5. Thomas Aquinas's version of the real distinction was explicitly developed in dialogue with Avicenna and against Averroes, who denied that existence was distinct from essence in creatures. The debate is one of the defining controversies of Scholastic metaphysics.