Any two points in a Stone space can be disconnected by clopen sets

Before proving the fact you want, we'll need the notion of quasicomponents and some basic propositions about it. In these terms, you are just asking if distinct points are in distinct quasicomponents. Let $X$ be a topological space. Given $x,y \in X$, define $x \sim y$ if $X$ cannot be written as a disjoint union of open sets $U$ and $V$ containing $x$ and $y$, respectively. It is straightforward to verify that $\sim$ is an equivalence relation. The equivalence classes are called the quasicomponents of $X$. It's easy to prove that the quasicomponent of a point $x$ is the intersection of all closed-open subsets of $X$ containing $x$.

In every topological space, the component $C$ of a point $x$ is contained in the quasicomponent $Q$ of the point $x$. In fact, if $F$ is a closed-open set containing $x$, then $X = F \cup (X-F)$ is a separation of $X$. Since $C \cap F \ne \emptyset$, it follows that $C \subseteq F$. Thus we have $C \subseteq Q$.

I'll prove now, based on Engelking's proof in the book General Topology, that in every compact Hausdorff space, components and quasicomponents coincide. Let $C$ and $Q$ as above. We just need to prove that the quasicomponent $Q$ is connected. Then will follow that $ Q = C$. Suppose that $Q = X_1 \cup X_2$, where $X_1, X_2$ are two disjoint closed subsets of the space $Q$. Then $X_1$ and $X_2$ are closed in $X$, since $Q$ is closed in $X$. By normality of compact Hausdorff spaces, there exist disjoint open subsets $U,V$ of $X$ containing $X_1, X_2$, respectively. Hence, we have $Q \subseteq U \cup V$ and, by compactness, there exist closed-open sets $F_1, \ldots, F_k$ such that

$$Q \subseteq \bigcap_{i=1}^k F_i \subseteq U \cup V.$$

$F = \bigcap_{i=1}^k F_i$ is clearly closed-open. Since $ \overline{U \cap F} \subseteq \overline{U} \cap F = \overline{U} \cap (U \cup V) \cap F = U \cap F$, the intersection $U \cap F$ is also closed-open. As $x \in U \cap F$, we have $Q \subseteq U \cap F$ and $X_2 \subseteq Q \subseteq U \cap F \subseteq U$. It follows that $X_2 \subseteq U \cap V = \emptyset$, which shows that the set $Q$ is connected.

Now it's simple to prove your statement. Let $B$ be a Stone Space. Since $B$ is compact Hausdorff, quasicomponents coincide with components. $B$ is totally disconnected, so the quasicomponent of a point $a \in B$ is $\{a \}$. If $b \in B$ is a different point, then $b$ isn't in the quasicomponent of $a$. Thus there exist disjoint open sets $U,V$ containing $a,b$, respectively, such that $B = U \cup V$.

Added This was motivated by Pete's answer. Actually, to prove that a locally compact Hausdorff totally disconnected space $X$ is zero-dimensional, we just need what I've proved for compact Hausdorff spaces. Indeed, let $x \in X$ and $U$ an open set containing $x$. Since $X$ is regular, there is an open set $V$ containing $x$ such that $\overline{V}$ is compact and $\overline{V} \subseteq U$. Also, $\overline{V}$ is a totally disconnected space. Using the fact that quasicomponents and components coincide in compact Hausdorff spaces, we have that the quasicomponent of $x$ in $\overline{V}$ is $\{x\}$. Now, the compactness of $\overline{V}$ guarantees that there are closed-open sets $F_1, \ldots, F_k$ such that $x \in F_1 \cap \cdots \cap F_k \subseteq V$. Let $F$ be $\bigcap_{i=1}^k F_i$. Then $F \,$ is an open set in $V$ and since $V \, $ is open in $X$, $F \, $ is open in $X$. Also, $F \,$ is compact, since each $F_i$ is a closed subset of the compact space $\overline{V}$, and then $F\,$ is closed in $X$. We conclude that for each open set $U$ containing $x$, there is a closed-open set $F \ $ such that $x \in F \subseteq U$. Thus $X$ is zero-dimensional.

The point of this answer is mostly to provide some terminology with which to express the distinction here.

A topological space is totally disconnected if the only nonempty connected subsets are the singleton sets. Equivalently, the connected components are all singleton sets.

A topological space is zero-dimensional if it admits a base of clopen [i.e., both open and closed] sets.

A topological space is separated (more traditionally: $T_1$) if all the singleton sets are closed.

First easy observation: A totally disconnected space is separated.

(Proof: Otherwise the closure of a point would give a larger connected component.)

Second easy observation: In a separated zero-dimensional space $X$, for any two distinct points $x_1$, $x_2$, there exists a separation $X = U_1 \coprod U_2$ with $x_i \in U_i$. (In the terminology of Nuno's answer -- which is relatively standard if not well-known -- the conclusion is that the quasi-components are singleton sets.) In particular, $X$ is totally disconnected.

(Proof: Let $x_1$, $x_2$ be distinct points in $X$. Since $X$ is separated, $N = X \setminus \{x_2\}$ is open. By definition of a base, there exists a clopen set $U_1$ with $x_1 \in U_1 \subset N$ and then $U_1$, $U_2 = X \setminus U_1$ is the desired separation.)

By contrast, we have the following

Nontrivial result: A locally compact Hausdorff space is zero-dimensional iff it is totally disconnected. For instance this wikipedia article gives a reference.

Note that Nuno's answer (which should be the accepted one, IMO) gives a proof of this in the compact case.

Perhaps a cleaner approach is to "redefine" a Stone space to be a space which is compact, Hausdorff and zero-dimensional. Then when you are given a space that someone says is a Stone space, the first thing you'll do is look for a base of clopen sets, which tends to be a good idea anyway. For instance, given any profinite space (i.e., an inverse limit of finite discrete spaces, yet another term for the same class of spaces!) it is very easy to do this.