How to do multiple lines within braces?

You can set the multi-row contents using an array:

\documentclass{article}

\usepackage{braket}

\begin{document}

\[
  A = \left\{ b\ \middle\vert \begin{array}{l}
    C, d \\
    e, F, g
  \end{array}\right\}
\]

% Using braket; see http://tex.stackexchange.com/q/32051/5764
\[
  A = \Set{ b\ | \begin{array}{l}
    C, d \\
    e, F, g
  \end{array}}
\]

\end{document}

You should define a unique structure for this kind of objects and I propose a variant of the \Set command described in the documentation of mathtools.

\documentclass{article}
\usepackage{mathtools,bm}

\providecommand\given{} % ensure it exists
\newcommand\givensymbol[1]{%
  \nonscript\;\delimsize#1\allowbreak\nonscript\;\mathopen{}%
}
\DeclarePairedDelimiterX\Set[1]\{\}{%
  \renewcommand\given{\givensymbol{\vert}}%
  #1%
}

\begin{document}
\begin{gather*}
\Set{x\given y} \\
\Set[\big]{x\given (a+b)c} \\
\Set*{z \given
  \begin{aligned}
  & 1\le z_{(k,m)}^{l}\le 1+a_{(k,m)}^{l}\gamma_{(k,m)}^{l}(\bm{p}) \\
  & \forall k\in\mathcal{K}, \forall m\in\mathcal{M},
    \forall l\in\mathcal{L}, \forall\bm{a}\in\mathcal{A}^{\dagger},
    \forall \bm{p}\in\mathcal{P}
  \end{aligned}
}
\end{gather*}
\end{document}

For example:

\documentclass{article}

\usepackage{amsmath}
\begin{document}

\[
\mathcal{Z}=\left\{
z \biggm| \begin{array}{l}
1\leq\\
\forall k
\end{array}
\right\}
\]

\end{document}

Please observe, that there should be \biggm|, not simply \bigg|, giving the proper space. (Observe \middle\vert, not \vert, in Werner's answer).