What does it mean for a density operator to be non-negative?

It means that all the eigenvalues are nonnegative, or equivalently $\langle \psi | \rho | \psi \rangle \geq 0$ for any vector $| \psi \rangle$ in the Hilbert space. See https://en.wikipedia.org/wiki/Positive-definite_matrix.

Whether or not the matrix elements of a finite-dimensional operator are nonnegative depends on the choice of basis, so non-negativity of matrix elements is not a very physically interesting property.

To add to Tparker's correct answer, the physical meaning of these conditions is, of course, that the eigenvalues of a density matrix are the probabilities defining the mixture of pure quantum states. The density matrix can be written:

$$\rho = \sum\limits_k p_k \left.\left|\hat{\psi}_k\right.\right>\left<\left.\hat{\psi}_k\right|\right.\tag{1}$$

where the $\left\{\hat{\psi}_k\right\}_k$ are an orthonormal basis spanning the quantum state space. The classical mixture mixes these pure states with probabilities $p_k$. That the $\hat{\psi}_k$ can be chosen orthonormal is assured by the operator's being Hermitian; (1) then of course expands the operator as a sum of projectors onto the basis members weighted by the eigenvalues.

So, the conditions simply assert that we can interpret the eigenvalues as positive probabilities summing to unity (recall that the trace is the sum of all eigenvalues). This condition is of course necessary for the operator to be a density matrix.

It can be shown that even if the mixed pure states are not orthonormal, if the density matrix is assembled as a sum of projectors with positive weights summing to unity as in (1) (but with the $\hat{\psi}_k$ not neeedfully orthonormal), then if the pure states are resolved into an orthonormal basis, the resulting expression analogous to (1) still has positive weights summing to unity (I still need to find a reference for this last assertion).