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 (1962), 1-54.  (The original Russian article is from 1949.  A pdf of the English translation is presently available [here][1].)
 - [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$.  Since we're already using the word "separable" for **(S)**, let's say that in this case $(S,\mu)$ is *one-sided countably generated*, and denote this property by **(CG1)**.  To keep terminology manageable, we won't explicitly say "mod zero", but this is understood, and thus we need to specify "one-sided" because of the restriction that $A\subset B$, which means that the "mod zero" only applies to the outer approximation, whereas the inner must be exact.

So that's two conditions.  Let's round it out by saying that $(S,\mu)$ is *one-sided separable* if it has a countable subset $\Gamma$ that is not only dense w.r.t. $\rho$ but also has the property that for every $A\in S$ and $\epsilon>0$ there exists $B\in \Gamma$ such that $A\subset B$ and $\mu(B\setminus A) < \epsilon$; we denote this property by **(S1)**.  Similarly, say $(S,\mu)$ is *countably generated* if it has a countable subset $\Gamma$ such that for every $A\in S$ there exists $B\in \sigma(\Gamma)$ such that $\rho(A,B)=0$.

Now we have four conditions: two of them involve approximations from the outside, while the other two allow arbitrary approximations.  Clearly **(CG1)** implies **(CG)**, and similarly **(S1)** implies **(S)**.  It was shown in [JDH] that **(CG)** implies **(S)**, but the converse is not true.

So far this is just a summary of what others have already said here.  Here's the new bit.

**Equivalence when non-atomic.**  Recall that an *atom* is a set $E\in S$ such that $\mu(E)>0$ and every subset $A\subset E$ has either $\mu(A)=0$ or $\mu(A)=\mu(E)$.  If $(S,\mu)$ is non-atomic (has no atoms), then in fact all four definitions are equivalent.  To see this, observe that any of the four imply **(S)**, and that **(S)** in turn implies that there is a $\sigma$-algebra isomorphism from $(S,\mu)$ to the Lebesgue sets on the unit interval equipped with Lebesgue measure [Ha, Sec. 41, Theorem C].  Since all four properties hold for the Lebesgue space, we are done.

**Atomic pieces.**  Intuitively, one expects that if $E$ is an atom in $(S,\mu)$, then there should be a $\sigma$-algebra map $(S|_E, \mu|_E) \to (T,\nu)$ that is a mod zero isomorphism, where $T$ is a $\sigma$-algebra with only two elements ($\emptyset$ and a single point) and $\nu$ is a point mass with total weight $\mu(E)$.  In particular, this requires that there exists a set $F\subset E$ such that $\mu(F) = \mu(E)$ and every null set $A\subset E$ has $A\cap F = \emptyset$.  The example in [JDH] shows that this need not always be the case, and that an atomic space need not be (mod zero) isomorphic to a point mass even if **(S)** holds.

The one-sided conditions **(S1)** and **(CG1)** serve to fill this gap and let us deal appropriately with the atomic pieces.  Indeed, if either of these properties hold, then one can show the following:

> **(A)** There exist atoms $E_n \in S$ such that $S|_{E_n}$ is the trivial $\sigma$-algebra for every $n$, and $S|_{(\bigcup_n E_n)^c}$ is isomorphic to the Lebesgue sets on an interval of length $1 - \sum_n \mu(E_n)$.

So at the end of the day, we see that **(CG1)** and **(S1)** are equivalent, and imply both **(CG)** and **(S)**.  Furthermore, **(CG)** implies **(S)**, and the converse is true if $(S,\mu)$ is non-atomic, but may fail if it has atoms.

I don't know if **(CG)** is equivalent to **(CG1)** and **(S1)**.  I suspect it is not, because otherwise I doubt that [Ro] would introduce the extra condition that $A\subset B$.  However, I do not know a counterexample.


*Comments on the proof of **(A)**.*  For the proof of **(A)**, one must use **(CG1)** or **(S1)** to take an atom $E\in S$ and produce a subset $F\subset E$, $F\in S$ such that $F\cap A = \emptyset$ for all $A\in S$ with $\mu(A)=0$.  The key to this is that both conditions allow you to produce a countable family $S'\subset S$ such that for every $\epsilon>0$ and every null set $A$, we have $A\subset \bigcup_n B_n$ for some $B_n \in S'$ with $\mu(\bigcup_n B_n) < \epsilon$.  (For **(S1)** one takes $S' = \Gamma$, while for **(CG1)** one takes $S'$ to be the set of all finite intersections of sets in $\Gamma$ and their complements.)  Then because $E$ is an atom, we can conclude that $\mu(B_n \cap E) = 0$ for all $n$, and so the collection of all null sets in $E$ can be covered by a *countable* collection of null sets, whose union therefore has measure zero.


  [1]: http://ma.huji.ac.il/~matang02/rohlin.pdf