In Peter Johnstone's book Stone Spaces, on page 53, we have the following corollary.

$\mathbf{Corollary}$ Every frame is isomorphic to a subframe of a complete Boolean algebra.

Of course by a subframe, we mean a subset that contains $0,1$ is closed under arbitrary joins and finite meets.

$\large\mathbf{Added} (10/19/13)$

I will outline two ways in which a frame can be embedded into a complete Boolean algebra.

Recall that a Nucleus on a frame $L$ is a mapping $\nu:L\rightarrow L$ such that $x\leq\nu(x)=\nu(\nu(x))$ and $\nu(x\wedge y)=\nu(x\wedge y)$. If $L$ is a frame, then the set $N(L)$ of Nuclei on $L$ is itself a frame.

If $M$ is a frame, then let $B_{M}=\{x^{**}|x\in M\}$ where $x^{*}$ denotes the pseudocomplement of $x$. Then $B_{M}$ is a complete Boolean algebra. If $(X,\mathcal{T})$ is a topological space, then $B_{\mathcal{T}}$ is the regular open algebra of the space $\mathcal{T}$. The mapping $x\mapsto x^{**}$ is a frame homomorphism.

If $L$ is a frame and $a\in L$, then the mapping $c(a):L\rightarrow L$ defined by $c(a)(x)=a\vee x$ is a Nucleus. Furthermore, the mapping $c:L\rightarrow N(L)$ is a frame homomorphism and each $c(a)$ is a complemented element of the frame $L$. In particular, the mapping $L\rightarrow B_{N(L)},a\mapsto c(a)^{**}$ is an injective frame homomorphism, so $L$ can be embedded as a subframe of the complete Boolean algebra $B_{N(L)}$. This embedding of a frame is the one given in Johnstone's book Stone Spaces.

There is another way to embed a frame in a complete Boolean algebra that I just thought of.

Let $\mathfrak{b}(a)=\{x\rightarrow a|x\in L\}=\{x|x=(x\rightarrow a)\rightarrow a\}$. Then each $\mathfrak{b}(a)$ is a complete Boolean algebra. Let $\phi:L\rightarrow\prod_{a\in L}\mathfrak{b}(a)$ be the mapping where $\phi(x)=((x\rightarrow a)\rightarrow a)_{a\in L}$ for each $x\in L$. Then $\phi$ is an injective frame homomorphism and clearly
$\prod_{a\in L}\mathfrak{b}(a)$ is a complete Boolean algebra.

$\large\mathbf{Added} (8/23/13)$
In Emil Jeřábek's answer, it is shown that every Heyting algebra can be embedded into a complete Boolean algebra such that the embedding preserves all least upper bounds and finite greatest lower bounds. This fact can be extending to a broader class of posets besides Heyting algebras which I shall call pre-frames.

A pre-frame is a poset $A$ such that if $R\subseteq A$, $\bigvee R$ exists and $x\leq\bigvee R$, then there is some $S\subseteq A$ with $S\preceq R$ and $\bigvee S=x$. It is easy to see that a meet-semilattice $A$ is a pre-frame if and only if whenever $R\subseteq A$,$\bigvee R$ exists, and $a\in A$, then $\bigvee_{r\in R}(a\wedge r)$ exists, and $a\wedge\bigvee R=\bigvee_{r\in R}(a\wedge r)$.

Essentially, a pre-frame is a poset which looks like a frame except for the fact that suprema and infima do not necessarily exist. A poset is a frame if and only if it is a complete lattice and a pre-frame.

I shall now show that every Heyting algebra is a pre-frame, but this fact requires some basic facts about Galois adjoints.

Recall that if $A,B$ are posets, then $f:A\rightarrow B$ is a left-Galois adjoint to $g:B\rightarrow A$ if $f(a)\leq b\Leftrightarrow a\leq g(b)$. It is not to hard to show that all left-Galois adjoints preserve all least upper bounds. In other words, if $R\subseteq A$ and $\bigvee R$ exists, then $f[R]$ has a least upper bound and $\bigvee f[R]=f(\bigvee R)$.

If $X$ is a Heyting algebra, then $c\wedge a\leq b$ iff $c\leq a\rightarrow b$. Therefore, if we define $f_{a},g_{a}$ by $f_{a}(c)=a\wedge c$ and $g_{a}(b)=a\rightarrow b$, then $f_{a}(c)\leq b$ if and only if $c\leq g_{a}(b)$. Therefore, the mappings $f_{a}$ is a left-Galois adjoint to the mapping $g_{a}$. In particular, the mapping $f_{a}$ preserves all least upper bounds. Said differently, if $I$ is an index set and $b_{i}\in X$ for $i\in I$ and $\bigvee_{i\in I}b_{i}$ exists, then $\bigvee_{i\in I}(a\wedge b_{i})$ exists, and $a\wedge\bigvee_{i\in I}b_{i}=\bigvee_{i\in I}(a\wedge b_{i})$. Therefore, every Heyting algebra is a pre-frame.

$\mathbf{Theorem}$ Let $A$ be a pre-frame. Let $\mathcal{C}$ denote the collection of all downwards closed subsets of $A$ which are closed under taking all least upper bounds. Then $\mathcal{C}$ is a frame. Furthermore, the mapping $e:A\rightarrow\mathcal{C}$ given by $e(a)=\downarrow a$ is an order preserving map that preserves all least upper bounds and all greatest lower bounds.

$\mathbf{Proof}$ Clearly $\mathcal{C}$ is a complete lattice.

Now assume that $L\subseteq A$ is a lower set. Then I claim that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}\in\mathcal{C}$. Clearly, $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$ is closed under taking all least upper bounds. To see that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$ is downwards closed, we take note that if $x\leq\bigvee R$ for some $R\subseteq L$, then $x=\bigvee S$ for some $S$ with $S\preceq R$. Since $R\subseteq L,S\preceq R$, and $L$ is a lower set, we have $S\subseteq L$ as well. Therefore $x\in\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$. We conclude that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}\in\mathcal{C}$.

To prove that $\mathcal{C}$ is a frame, assume that $L\in\mathcal{C}$ and $L_{i}\in\mathcal{C}$ for $i\in I$. Clearly,
$\bigvee_{i\in I}(L\cap L_{i})\subseteq L\cap\bigvee_{i\in I}L_{i}$. For the other direction, assume that $x\in L\cap\bigvee_{i\in I}L_{i}$. Then $\bigcup_{i\in I}L_{i}$ is a lower set. Therefore, $\{\bigvee R|R\subseteq\bigcup_{i\in I}L_{i},\bigvee R\,\mathrm{exists}\}$ is the least element in $\mathcal{C}$ containing $\bigcup_{i\in I}L_{i}$. In other words, $\{\bigvee R|R\subseteq\bigcup_{i\in I}L_{i},\bigvee R\,\mathrm{exists}\}=\bigvee_{i\in I}L_{i}$ where the least upper bound is taken in $\mathcal{C}$. Therefore, we have $x=\bigvee R$ for some $R\subseteq\bigcup_{i\in I}L_{i}$. However, since $x=\bigvee R\in L$ and $L$ is a lower set, we have $R\subseteq L$. Therefore, since $R\in L\cap\bigcup_{i\in I}L_{i}=\bigcup_{i\in I}(L\cap L_{i})$, we have $x=\bigvee R\in\bigvee_{i\in I}(L\cap L_{i})$. We conclude that
$L\cap\bigvee_{i\in I}L_{i}\subseteq\bigvee_{i\in I}(L\cap L_{i})$. Therefore $\mathcal{C}$ is a frame.

The fact that $e$ preserves all suprema and infima is fairly trivial.
To see that the mapping $e$ preserves all greatest lower bounds, we simply observe that by definition $\downarrow(\bigwedge R)=\bigcap_{r\in R}\downarrow r$. Furthermore, if $a_{i}\in A$ for $i\in I$ and $\bigvee_{i\in I}a_{i}$ exists, then clearly $\bigvee_{i\in I}(\downarrow a_{i})=\downarrow(\bigvee_{i\in I}a_{i})$. $\mathbf{QED}$

In particular, since every frame is isomorphic to a subframe of a complete Boolean algebra, every pre-frame $L$ can be embedded in a complete Boolean algebra in a way so that the embedding preserves finite meets and all joins that exist in $L$.

meetsas well as joins unless finite joins distribute over infinite meets (which fails in general). (3) An embedding of a locale in anatomiccomplete Boolean algebra preserving all joins and finite meets exists iff the locale isspatial. I see no reason why this condition should be necessary for non-atomic Boolean algebras. $\endgroup$ – Emil Jeřábek Aug 19 '13 at 14:00