We consider how to quantify non-Gaussianity for the correlation of a bipartite quantum state by using various measures such as relative entropy and geometric distances. We first show that an intuitive approach, i.e., subtracting the correlation of a reference Gaussian state from that of a target non-Gaussian state, fails to yield a non-negative measure with monotonicity under local Gaussian channels. Our finding clearly manifests that quantum-state correlations generally have no Gaussian extremality. We therefore propose a different approach by introducing relevantly averaged states to address correlation. This enables us to define a non-Gaussianity measure based on, e.g., the trace-distance and the fidelity, fulfilling all requirements as a measure of non-Gaussian correlation. For the case of the fidelity-based measure, we also present readily computable lower bounds of non-Gaussian correlation.