"fact of being imprisoned," 1530s, from Medieval Latin incarcerationem (nominative incarceratio), noun of action from past-participle stem of incarcerare "to imprison," from in- "in" (from PIE root *en "in") + carcer "prison, an enclosed space," from Proto-Italic *kar-kr(o)-, which is of uncertain origin.
It seems best to connect carcer with other IE words for 'circle, round object', such as [Latin] curvus, [Greek] κιρκος 'ring', [Old Norse] hringr, although not all of these have a good IE etymology. The reduplication in Latin carcer could be iconic; thus, the original meaning would have been 'enclosure'. [de Vaan]
The word appears earlier in English in an obsolete medical sense of "retention of pus" (early 15c.).
Figurative use, "to nullify (an obligation, etc.)" is from mid-15c. Related: Canceled (also cancelled); cancelling.