(I'm not an expert in this subject, but here's my understanding.)
The BCH code of code length $n=2^m-1$ and designed distance $2t+1$ is specified in terms of its generator polynomial. Fix $\alpha$ to be a primitive element of $GF(2^m)$. Then, $g$ is the polynomial of smallest degree with coefficients in $GF(2)$ which has its roots $\alpha, \alpha^2,\alpha^3,\dots,\alpha^{2t}$. (The codewords are then given by all multiples of $g$ of degree at most $n-1$; see the wikipedia page for polynomial codes). The designed distance is a lower bound on the distance of the code.
The dual BCH code of design distance $2t+1$ is just the dual of the BCH code in the usual sense, the set of vectors orthogonal to the codewords of the BCH code of design distance $2t+1$. Its generator polynomial is given by $(X^n+1)/g(X)$. I believe the matrix in the Ailon-Liberty paper has the codewords as its rows.
Here are some notes which describe the BCH code construction: http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf