When do elements in the braid group $B_n$ commute? I have been looking around for an answer to this question, but I have not been able to find anything. My question is:
Is it known how to tell whether two elements $b_1, b_2 \in B_n$ commute?
EDIT: Is there perhaps a nicer/cleaner rule for $B_3$ and $B_4$?
 A: One approach to this question is to try to give a description of the centralizer. This can be done using the Nielsen-Thurston classification of elements in mapping class groups. 
To describe this in this case, first note that the braid group $B_n$ is the mapping class group of the $n$-punctured disk. Then $B_n/\Delta_n$ is a subgroup of the mapping class group of an $n+1$-punctured sphere, where $\Delta_n$ is a full twist, generating the center of the braid group (and corresponding to a Dehn twist about the boundary of the disk). 
Hence if one can describe the centralizer of the image of an element in the mapping class group of an $n+1$-punctured sphere, then one can describe the centralizer in $B_n$ by taking the preimage. 
The Nielsen- Thurston classification then says that every element is either reducible, finite-order, or pseudo-Anosov. The normalizers of pseudo-Anosovs are virtually cyclic groups, generated by minimal pseudo-Anosov and its symmetries, and the centralizer is finite index in the normalizer.
If a mapping class is finite order, then it is realized by a finite-order homeomorphism, and the centralizer is related to the mapping class group of the quotient surface (punctured at the fixed points). This can be described then by induction. 
If a mapping class is reducible, then there is a minimal set of curves which are preserved by the element up to isotopy (corresponding to the JSJ decomposition of the mapping torus), and the action on the mapping class groups of the complementary components are either finite order or pseudo-Anosov (taking into account the permutation action on components). The centralizer here then can be described inductively by considering the centralizer of the action on the complement of the reducing curve and the Dehn twists about these curves. 
Applying this to the braid group, this means that we can conjugate any element so that it looks like braids on sub collection of strands, which in turn are braided together, etc. The centralizers then have a description (up to finite index) as products of centralizers of the subbraids (which are either virtually cyclic or virtually braid groups),  product with Dehn twists about the multi curves. All this is complicated by how the reducing curves are permuted, which must be taken into account in the final description. I wouldn’t be surprised if this can be found in the literature; I would consult Farb-Margalit’s primer.
A: You are asking: "Suppose that a and b are braids, with inverses A and B.  Is the element abAB trivial?"  
This is a special case of the word problem for the braid group, which has many solutions.  Perhaps Artin's 1947 paper (Theorems 17 and 18) is the first.  Many of the papers mentioned by other answers in the thread also "quickly" give solutions to the word problem (eg for linear groups over $\mathbb{Z}$, for groups acting on free groups, etc). 
A: By reading Wikipedia page on braid group one finds the Larence-Krammer representation. This makes one wonder whether there are maybe simpler faithfull representation for small $n$ and indeed, reading the corresponding paragraph, it seems that there is hope given by Burau representation which was conjectured to be faithful for a long time. However, it is not faithful for $n\geq 5.$ This last Wikipedia page links to a review article Faithful representations of the braid groups by Vladimir Turaev in which he states that the Burau representation is indeed faithful for $n\leq 3$ and that the case $n=4$ is open. So was there any progress in the last almost 20 years since the article was written? Quick googling suggests that some people are still working on it and that they seem to believe that it is indeed faithful. See the work of Beridze and Traczyk and Attacks on the Faithfulness of the Burau Representation of the Braid Group $B_4$ by Abdulrahim and Chreif.
A: Krammer ("The braid group $B_4$ is linear", Invent. Math. 142 (2000), 451–486 (MSN)) constructed
a representation $\rho: B_n \to {\rm GL}_N({\bf Z}[q^{\pm 1}, t^{\pm 1}])$
with $N = {n \choose 2}$, and Bigelow ("Braid groups are linear", J. AMS 14 #2 (2000), 471–486 (MSN))
proved it is faithful for all $n$.  Thus $b_1,b_2 \in B_n$ commute
if and only if $\rho(b_1)$ and $\rho(b_2)$ commute in
${\rm GL}_N({\bf Z}[q^{\pm 1}, t^{\pm 1}])$,
which is a finite computation.
A: $\DeclareMathOperator\Aut{Aut}$Here is an easier computation: $B_n$ admits a faithful representation into the automorphism group of a free group of rank $n$, $\rho\colon B_n  \to \Aut(F_n)$. I learned this from a paper of Birman; the result might be older. Fix a free basis $x_1,\dotsc,x_n$. The image of the $i$th standard generator $\sigma_i$ in $\Aut(F_n)$ is defined by its action on the basis as follows.
$$\rho(\sigma_i)=\begin{cases} x_i \quad\mapsto x_ix_{i+1}x_i^{-1} \\ x_{i+1} \ \mapsto x_i \\ x_j \quad\mapsto x_j & j \notin \{i,i+1\}\end{cases}$$
Conversely any automorphism permuting the conjugacy classes of the $x_i$ and fixing the word $x_1x_2\dotsb x_n$ is in the image of the representation.
Therefore to check whether $a$ and $b$ commute in $B_n$, as in Noam's answer, one need only check whether $\rho(a)$ and $\rho(b)$ commute, or equivalently if the action of $\rho(ab)$ on the free basis is equal to that of $\rho(ba)$.

ETA: More intrinsically, there are various normal forms one could put $ab$ and $ba$ in and check whether they are equal. Dehornoy has a survey, "Efficient solutions to the braid isotopy problem". I guess the keywords I'm aware of are "Garside structure," "left-greedy" and "combing". The left-greedy normal form is discussed by Bestvina in "Non-positively curved aspects of Artin groups of finite type", although I gather that it is due to Thurston.
