The Stern polynomials defined by $s(0;x)=0$, $s(1;x)=1$, and for $n\geq 1$ by $s(2n;x)=s(n;x^2)$ and $s(2n+1;x)=x\,s(n;x^2)+s(n+1;x^2)$ have only 0 and 1 as coefficients. We construct an infinite lower-triangular matrix related to the coefficients of the $s(n;x)$ and show that its inverse has only 0, 1, and $-1$ as entries, which we find explicitly. In particular, the sign distribution of the entries is determined by the Prouhet-Thue-Morse sequence. We also obtain other properties of this matrix and a related Pascal-type matrix that involve the Catalan, Stirling, Fibonacci, Fine, and Padovan numbers. Further results involve compositions of integers, the Sierpiński matrix, and identities connecting the Stern and Prouhet-Thue-Morse sequences.