There are many relevant papers, but the most convenient book to consult is:
MR1778802 (2002k:20017) 20C15 (20C08 20F55),
Geck, Meinolf (F-LYON-GD); Pfeiffer,G¨otz (IRL-GLWY)
Characters of finite Coxeter groups and Iwahori-Hecke algebras.
London Mathematical Society Monographs. New Series, 21.
The Clarendon Press, Oxford University Press, New York, 2000. xvi+446 pp.
See also their earlier paper: MR1250466 (94m:20018) 20C15,
Geck, Meinolf (D-AACH-DM); Pfeiffer,G¨otz (D-AACH-DM),
On the irreducible characters of Hecke algebras.
Adv. Math. 102 (1993), no. 1, 79–94.
In the last chapter of my book Reflection Groups and Coxeter Groups (Cambridge, 1990) there is a brief summary of earlier work done on irreducible
representations or character tables of finite Coxeter groups and their Iwahori-Hecke algebras. The 1979 Kazhdan-Lusztig paper was partly motivated by earlier papers of people like Iwahori and Curtis, but especially by Springer's theory of Weyl group representations on cohomology of flag varieties. The powerful "cell" construction by Kazhdan-Lusztig does not in general give explicitly the irreducible representations, however. Carter's 1985 book on characters of finite groups of Lie type discusses how all of this feeds into that kind of representation theory. Much of the progress has been due to Lusztig.
It's important to distinguish between finite crystallographic Coxeter groups (Weyl groups) and the remaining dihedral groups along with exceptions $H_3, H_4$. Even in the latter cases, much of the Weyl group theory has good analogues in spite of being outside the classical framework of groups of Lie type. In any case, whether the results in the literature are explicit enough for some purposes may be an open question. Certainly the case of symmetric groups and their Iwahori-Hecke algebras has been developed most concretely.
Let $K$ be a field. The literal answer has already been given by several people but let me try and get at the algebraic structure and provide a quiver with relations (see the addition). Let $J$ be the $n\times n$ all ones matrix. Then $J$ centralizes $S_n$ and the centralizer of $J$ consists of all matrices whose rows and columns all sum to some fixed field element $k\in K$. This has dimension $(n-1)^2+1$ and several people have proved the subalgebra spanned by $S_n$ has this dimension so $B_n$ is the centralizer of $J$.
If the characteristic of $K$ is zero or does not divide $n$, then we can change the basis to consists of $(1,\cdots,1)$ and $e_1-e_i$ with $2\leq i\leq n$ with $e_i$ standard basis vectors. Then $J$ becomes the elementary matrix $E_{11}$ in this basis and its centralizer is clearly $K\times M_{n-1}(K)$, which can also be seen by representation theory. This is a split semisimple algebra with two simple modules and there is nothing much to say.
If $K$ has characteristic $p$ dividing $n$, then $J^2=0$ and it is easy to see the Jordan canonical form of $J$ is a $2\times 2$ block and $n-2$ blocks that are $1\times 1$. In fact the basis $e_1,(1,\ldots, 1), e_i-e_1$ for $2\leq i\leq n-1$ gives the Jordan form with $e_1,(1,\ldots,1)$ giving the $2\times 2$-block. Thus we can identify $B_n$ with the centralizer of $$J'=N_2\oplus 0_{n-2}$$ where $N_2= \begin{bmatrix} 0 & 0\\ 1&0\end{bmatrix}$. A more ring theoretic view is the following.
Let $R=K[x]/(x^2)$; its a self-injective local $K$-algebra and $K$ is the unique simple where $x$ acts by $0$. Then the centralizer of $J'$ is $\mathrm{End}_R(R\times K^{n-2})$. I claim the the semisimple quotient here is $K\times M_{n-2}(K)$ and hence there are two simple modules and the algebra $B_n$ is split over $K$. This is not to difficult to check directly since $R$ is a projective indecomposable $R$-module with simple quotient $K$ and simple socle $K$. Also note that the radical of $R$ is its socle. So the radical of $\mathrm{End}_R(R\times K^{n-2})$ is the direct sum of the $1$-dimensional radical of $R$ (viewed as endomorphisms of the first summand $R$), the $n-2$-dimensional space of $R$-module homomorphisms $R\to K^{n-2}$ and the $n-2$-dimensional space of $R$-module homomorphisms $K^{n-2}\to R$ (which all land in the one-dimensional socle=radical). From this description it is easy to see that the radical squares to $0$ which means that as soon as you know the quiver, you know the basic algebra. The semismple quotient is a copy of $K$ coming from $R/\mathrm{rad}(R)$ and the endomorphisms of the semisimple module $K^{n-2}$, which is $M_{n-2}(K)$. Note that any composition $K^{n-2}\to R\to K^{n-2}$ is zero since the socle of $R$ is its radical. But the compositions $R\to K^{n-2}\to R$ give the elements of $\mathrm{rad}(R)$ and so the radical cubed is zero.
If we view $B_n$ as the centralizer of $J$, then the radical (which has dimension $2n-3$) is spanned by those matrices where each row is a constant vector and each column sums to $0$ and those matrices where each column is a constant vector and each row sums to $0$. Hopefully a representation theorist can compute the basic algebra from this description.
Let me add that when $n=2=p$, this description recovers that $B_2\cong K[x]/(x^2)$ and when $n=3=p$, it recovers that $B_3$ is a basic algebra with semisimple quotient $K\times K$. I would guess in general that the basic algebra is $\mathrm{End}_R(R\times K)$ but I am not 100% sure.
Added and edited based on corrections by the OP and @JeremyRickard. If I am not mistaken, the quiver of $B_n$ when $p\mid n$ and $n>2$ has two vertices $v,w$. There is one edge from $v$ to $w$, one edge from $w$ to $v$.and one loop at $v$. Since its a radical-squared zero split algebra, the quiver presentation for the basic algebra then says that all paths of length $2$ are $0$. But an expert should check this. There is a relation saying the path of length two from $v$ to $v$ is zero. Indeed view $B_n$ as $A=\mathrm{End}_R(R\times K^{n-2})$. A complete set of orthogonal primitive idempotents are the projection $e$ to $R$ and the $n-2$ projections to $K$, but the latter $n-2$ all give isomorphic projective indecomposables so we just need one of them, say the projection $f$ to the first factor, for the quiver. Then since the radical squared is zero, to compute the quiver we have that $f\mathrm{rad}(A)e=fAe$ is one dimensional and so is $e\mathrm{rad}(A)f=eAf$ since there is a one-dimensional space of homomorphisms $R$ to $K$ and $K$ to $R$. Also $eAe\cong R$ but $e\mathrm{rad}(R$ is the radical squared as noted above and so $e(\mathrm{rad}(A)/\mathrm{rad}^2(A))e\cong 0$. On the other hand, $fAf\cong K$ and so $f\mathrm{rad}(A)f=0$. This gives my description of the quiver. That the compositions $K\to R\to K$ are zero but $R\to K\to R$ are not all zero gives the relation.
Best Answer
I'm not sure I understand the first paragraph, but regarding the second I think this goes by the name of "Gelfand's trick", used to prove eg commutativity of the spherical Hecke algebra attached to $G=GL_n(Q_p)$ and $B=GL_n(Z_p)$ --- namely we first discover that we can write down coset representatives that are invariant under transposition (in this case diagonal matrices with powers of $p$ on the diagonal). Then we recall that transposition is an anti-isomorphism of the group algebra with itself. Thus the Hecke algebra is a subalgebra on which an anti-isomorphism acts as the identity, hence it is in fact commutative. The same trick will work in your general situation.