Kramer (Invent. Math. 142 (2000), 451-486) 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 (J. AMS 14 #2 (2000), 471-486) 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.

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.