From what I can tell, the word 'center' (or its German friend 'zentrum,' which is what gave us the notation $Z(G)$ that we use today) was introduced by JA de Seguier, in his 1904 textbook Elements de la theorie des groups abstraits.
This is interesting because it was also this textbook that thought to have created the name 'demi-groupe,' which later became semi-group, and eventually what we now call a semigroup.
I don't know of the original rationale behind choosing the word center, but there are a few possibilities that strike me. The ideas of algebras, algebra homomorphisms, and automorphisms were known. Here's a thought: were there yet 'inner automorphisms?' The phrase 'inner product' had been around since 1844, when Grassman developed different algebras of the hypercomplex numbers (in Die lineale Ausdehnungslehre, 1844). Interestingly, it seems that he chose these names more for their being antonyms, rather than an intrinsic meaning.
It happens to be that those simple algebras over a field with the property that every automorphism is an inner automorphism are precisely those that are called central (where the center as we know it today is exactly the base field). I like the idea that central and inner are related (even though it's not entirely founded).
In a similar vein, actions were in high fashion and few actions are as well-studied as conjugation. Kannappan's suggestion that those elements fixing elements under conjugation are the source of the name center seems reasonable as well.
But it is also possible that the naming convention falls closer to Polya than Grassman. Polya coined the term 'central limit theorem' in his paper (Über den zentralen Grenzwertsatz der Wahrscheinlichkeitsrechnung und das Momentenproblem), but it's believed that he named it 'central' because of its 'central importance' rather than any intrinsic quality. (Though it fits nicely with the intuition of things called measures of central tendency).
But these rationales are speculative.