The two definitions alluded to in the title can be found in the relevant Wikipedia entry (one is that the $\sigma$algebra is countably generated, the other is pretty much the standard usage of the word separable wrt the semimetric given by the measure). Why are they equivalent?

$\begingroup$ For convenience, I copied the Wikipedia article in a community wiki answer. $\endgroup$– François G. DoraisJun 8, 2010 at 18:43

$\begingroup$ I'm too lazy to try to prove this right now, but where does your proof get stuck? $\endgroup$– Nate EldredgeJun 8, 2010 at 19:16

$\begingroup$ Say the $\sigma$algebra is countably generated. How do I pick the countable dense subset in the semimetric given by $\mu(A\Delta B)$? $\endgroup$– Kestutis CesnaviciusJun 8, 2010 at 21:07

$\begingroup$ Kestutis, I explain how to do this in my updated answer. You can use the finite Boolean combinations of the generating set. $\endgroup$– Joel David HamkinsJun 9, 2010 at 2:31

$\begingroup$ As this is an important question I just want to summarise the key points from the different answers below: $(X,\mathcal{S},\mu)$ is a measure space. (I) The semimetric $\mu(A \triangle B)$ is separable if and only if $\exists$ countable set $\mathcal{S}_0 \subset \mathcal{S}$ s.t. $\mathcal{S} \subset \sigma(\mathcal{S}_0 \cup \mathcal{N}_\mu)$. (II) It is possible that the semimetric $\mu(A \triangle B)$ is separable but there is no countable set $\mathcal{S}_0 \subset \mathcal{S}$ s.t. $\mathcal{S} \subset \sigma(\mathcal{S}_0 \cup \mathcal{N}_{\mu_{\sigma(\mathcal{S}_0})})$. $\endgroup$– Julian NewmanFeb 23, 2017 at 18:01
4 Answers
The two notions are not equivalent. Indeed, they are not equivalent even when one considers completing the measure by adding all null sets with respect to any countably generated $\sigma$algebra. Nevertheless, the forward implication holds.
First, let me explain the forward implication. Suppose that $S$ is a $\sigma$algebra generated by a countable subfamily $S_0$ and $\mu$ is a finite measure defined on $S$. The semimetric on $S$ is defined by $d(A,B)=\mu(A\triangle B)$. Let $S_1$ be the collection of finite Boolean combinations of sets in $S_0$. This is a countable family, and I claim it is dense in the semimetric. To see this, let $S_2$ be the closure of $S_1$ in the semimetric, that is, the sets $A\in S$ that are approximable by sets in $S_1$, in the sense that for any $r\gt 0$ there is $B\in S_1$ such that $d(A,B)\lt r$. Note that $S_2$ contains $S_1$ and is closed under complement since the measure was finite. I claim it is also closed under countable unions: if each $A_n$ is approximable by $B_n$ to within $r/2^n$, then $\cup_n A_n$ is approximated by $\cup_n B_n$ to within $r$, and so one may find an approximating finite union. So $S_2$ is actually a $\sigma$algebra, and since it contains $S_0$, it follows that $S_2=S$. That is, every set in $S$ is approximable by sets in $S_1$, and so $S_1$ is a countable dense set in the semimetric, as desired.
Let's turn now to the reverse implication, which is not generally true. The easiest counterexample for this in the strict sense of the question is to let $X$ be a set of size continuum and $S=P(X)$, the full power set of $X$. This is a $\sigma$algebra, but it is easily seen not to be countably generated on cardinality grounds. Fix any $p\in X$ and let $\mu$ be the measure placing mass $1$ at $p$ and 0 mass outside {p}. In this case, the family {emptyset, X} is dense in the semimetric, since every subset is essentially empty or all of $X$, depending on whether it contains $p$. So the semimetric is separable, but the $\sigma$algebra is not countably generated.
Note that in this counterexample, the $\sigma$ algebra is obtained from the counting measure on {p} by adding a large cardinality set of measure $0$ and taking the completion. Similar counterexamples can be obtained by adding such large cardinality set of measure $0$ to any space and taking the completion.
At first, I thought incorrectly that one could address the issue by considering the completion of the measure, and showing that the $\sigma$algebra would be contained within the completion of a countably generated $\sigma$algebra. But I now realize that this is incorrect, and I can provide a counterexample even to this form of the equivalence.
To see this, consider the filter $F$ of all sets $A\subset \omega_1$ that contain a closed unbounded set of countable ordinals. This is known as the club filter, and it is closed under countable intersection. The corresponding ideal $NS$ consists of the nonstationary sets, those that omit a club, and these are closed under countable union. It follows that the collection $S=F\cup NS$, which are the sets measured by a club set, forms a $\sigma$algebra. The natural measure $\mu$ on $S$ gives every set in $F$ measure $1$ and every set in $NS$ measure $0$. This is a countably additive 2valued measure on $S$. Note that every set in $S$ has measure $0$ or $1$; in particular, there are no disjoint positive measure sets. It follows that the family {emptyset,$\omega_1$} is dense in the semimetric, since every set in $S$ either contains or omits a club set, and hence either agrees with emptyset or with the whole set on a club. Thus, the semimetric is separable. But for any countable subfamily $S_0\subset S$, we may intersect the clubs used to decide the members of $S_0$, and find a single club set $C\subset\omega_1$ that decides every member of $S_0$, in the sense that every member of $S_0$ either contains or omits $C$. This feature is preserved under complements, countable unions and intersections, and therefore $C$ decides every member of the $\sigma$algebra generated by $S_0$. The completion of the measure on the $\sigma$algebra generated by $S_0$ is therefore contained within the principal filter generated by $C$ together with its dual ideal. This is not all of $S$, since there are club sets properly contained within $C$, such as the set of limit points of $C$. Thus, this is a measure space that has a separable semimetric, but the $\sigma$algebra is not contained in the completion of any countably generated $\sigma$algebra.

$\begingroup$ Why is every $A\in S$ obtained by a union of the form you're claiming? $\endgroup$ Jun 8, 2010 at 21:01

$\begingroup$ Indeed, the Borel $\sigma$field on $\mathbb{R}$ is generated by the countable family of intervals with rational endpoints, but certainly not every Borel set is a countable union of such sets and their complements! (Any closed bounded set is already a counterexample.) $\endgroup$ Jun 8, 2010 at 21:41

$\begingroup$ Nate, of course you are right, since the closure process generally proceeds in an $\omega_1$ hierarchy, so this part of my argument is wrong. But I've realized that the equivalence is not correct even when one considers the completion, and I'll update my answer shortly to explain. $\endgroup$ Jun 8, 2010 at 23:36

$\begingroup$ I updated my argument. The example shows that from separability in the semimetric space, one cannot necessarily find the $\sigma$algebra in the completion of a countably generated $\sigma$algebra. $\endgroup$ Jun 9, 2010 at 1:31

$\begingroup$ I have now added a proof of the forward implication. $\endgroup$ Jun 9, 2010 at 2:32
The wikipedia article is misleading. These two definitions are not equivalent.
The first definition makes sense for the $\sigma$algebra of Borel sets on a topological space. If the space is Borel standard (that is, a Borel subset of a complete separable metric space), then it is countably generated. Note that a countably generated $\sigma$algebra in the sense of the first definition has the cardinal of the continuum, this is proven just as for the $\sigma$algebra of Borel set in [0,1], by a transfinite induction.
The second definition makes sense up to null sets. It is equivalent to saying that the algebra is generated by a countable collection of subsets, together with the null sets, and it is in my opinion a better definition. The collection of null sets (and their complementary sets) usually have a cardinality greater than the continuum if the $\sigma$algebra is complete w.r.t the measure, hence it is cannot be countably generated. Here again, you may think of the Lebesgue measurable sets in [0,1]. This is not countably separated in the sense of the first definition, for cardinality reasons, but this is countably generated in the sense of the second definition.
Now let me add a few words to explain what is going on with the second definition. Putting the metric $d(A,B)=\mu(A\Delta B)$ on the $\sigma$algebra amounts to embedding the $\sigma$algebra in $L^1$ with the map $A\rightarrow {\bf 1}_A$ and recovering the distance from the $L^1$ norm: $d(A,B)={\bf 1}_A{\bf 1}_B$. This should explain why the $\sigma$algebra is separable in the sense of the second definition if and only if $L^1$ itself is separable, and also prove that the collection of Lebesgue measurable sets is a separable $\sigma$algebra.

$\begingroup$ Why does the first definition only makes sense for $\sigma$algebra of Borel sets? Why is the second definition \emph{equivalent} to saying that the algebra is generated by a countable collection of subsets, together with the null sets? $\endgroup$ Jun 8, 2010 at 20:59

$\begingroup$ @Kestutis. I should have said: the first definition is useful when studying Borel sets, but is too restrictive when studying e.g. Lebesgue measurable sets. Now for the equivalence, this comes from the fact that any subset (in our case {1_A, A measurable}) of a separable metric space (in our case L^1) is separable. And from the fact that 1_{A_n} converges to 1_A in L1 norm iff A=limsup A_n=liminf A_n up to a negligible set. See e.g. the book of Dudley, "Real analysis and probability". $\endgroup$– coudyJun 8, 2010 at 21:29
[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), 154. (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 onesided 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), onesided 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.
Here is the Wikipedia text in question.
In mathematics, σalgebras are usually studied in the context of measure theory. A separable σalgebra (or separable σfield) is a sigma algebra that can be generated by a countable collection of sets. To learn what is meant by the σalgebra generated by a collection of sets, refer to the article on sigma algebras.
A separable measure space has a natural metric that renders it separable as a metric space. The distance between two sets is defined as the measure of the symmetric difference of the two sets. Note that the symmetric difference of two distinct sets can have measure zero; hence the metric as defined above is not a true metric. However, if sets whose symmetric difference has measure zero are identified into a single equivalence class, the resulting quotient set can be properly metrized by the above metric. If the measure space is separable, it can be shown that the corresponding metric space is, too.