$\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.
