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 \not\in \{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](https://arxiv.org/pdf/math/0703666.pdf). I guess the keywords I'm aware  of are "Garside structure," "left-greedy" and "combing". The left-greedy normal form is discussed by Bestvina [here](https://arxiv.org/abs/math/9812011), although I gather that it is due to Thurston.