[**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][1].]

----------

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][2].)
 - [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][3], 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][1]) -- 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.


  [1]: https://vaughnclimenhaga.wordpress.com/2015/10/22/lebesgue-probability-spaces-part-i/
  [2]:  https://web.archive.org/web/20160220162418/https://ma.huji.ac.il/~matang02/rohlin.pdf
  [3]: https://mathoverflow.net/questions/171845/question-on-separability-of-a-measure