Equivalently, all eigenvalues are positive. Positive semi-definite allows zeros.
Why it matters. A valid covariance matrix must be positive semi-definite, because x'Σx is the variance of a portfolio and variance cannot be negative.
The interview use. This is what makes some correlation structures impossible - three assets cannot all be pairwise correlated at -0.9. Asked "is this a valid correlation matrix?", the answer is a positive semi-definiteness check.
Sample estimates from short histories often fail it, which is why shrinkage is standard.