[Edited 10/22/15: there were embarrassing errors in my original answer, which were pointed out in another question; I've corrected these, and I've written up further details in a blog post.]
I'm late to the party, but here's my two cents. References in what follows are to
- [Ha] P.R. Halmos, Measure Theory, Springer, 1950.
- [Ro] V.A. Rokhlin, On the fundamental ideas of measure theory, Transl. AMS, Series 1, No. 10 (1952), 1-54. (The original Russian article is from 1949. A pdf of the English translation is presently available here.)
- [JDH] will denote the answer already given to this question by Joel David Hamkins.
Consider a measured $\sigma$-algebra $(S,\mu)$. Assume that $\mu$ is normalised to have total weight 1, and that $S$ is complete (contains all subsets of null sets).
In [Ha], $(S,\mu)$ is said to be separable if it has a countable subset that is dense w.r.t. the metric $\rho(A,B) = \mu(A\bigtriangleup B)$. We denote this property by (S).
In [Ro], $(S,\mu)$ is said to be separable if it has a countable subset $\Gamma$ such that for every $A\in S$, there exists $B\in \sigma(\Gamma)$ such that $A\subset B$ and $\mu(B\setminus A) = 0$. Here $\sigma(\Gamma)$ is the $\sigma$-algebra generated by $\Gamma$. (In fact, Rokhlin's definition is given for a measure space, not just a measured $\sigma$-algebra, and requires that $\Gamma$ separate points of the space.) Since we're already using the word "separable" for (S), let's say that in this case $(S,\mu)$ is one-sided countably generated mod zero, and denote this property by (CG0+).
So that's two conditions. Another natural condition would be that $S$ itself is countably generated, that is, that $S = \sigma(\Gamma)$ for some countable $\Gamma$; call this (CG), and not that it applies to the Borel $\sigma$-algebra on $[0,1]$, but not the Lebesgue $\sigma$-algebra. The latter satisfies the weaker condition (CG0+), and hence is also countably generated mod zero, meaning that there is a countable $\Gamma \subset S$ such that for every $A\in S$, there exists $B\in \sigma(\Gamma)$ such that $\mu(A \bigtriangleup B) = 0$.
(In the previous version of this answer I got carried away and also defined (S1), one-sided separability, to be the property that every $A\in S$ and $\epsilon>0$ there exists $B\in \Gamma$ such that $A\subset B$ and $\mu(B\setminus A) < \epsilon$. As was correctly pointed out by Rina Shora and Nik Weaver on another question, this fails to hold for even the most standard examples.)
It is immediate that (CG) $\Rightarrow$ (CG0+) $\Rightarrow$ (CG0), and [JDH] shows that (CG0) $\Rightarrow$ (S) (it is written with (CG) in mind, but works just as well for (CG0)). In fact one can also show that (S) $\Rightarrow$ (CG0) (details are in this blog post) -- that is, separability is equivalent to being countably generated mod zero -- and that the first two implications above are strict (the Lebesgue $\sigma$-algebra satisfies (CG0+) but not (CG), and the $\sigma$-algebra of Lebesgue subsets of $[0,1]$ with measure 0 or 1 satisfies (CG0) but not (CG0+)).
Finally, another related condition would be that $S$ is contained in the completion of a countably generated $\sigma$-algebra; this property lies somewhere between (CG) and (CG0), but its relation to (CG0+) is not clear to me. The example in [JDH] involving the club filter shows that (S) (and hence (CG0)) is not enough to imply this condition.