I'll try and sketch a construction. Firstly, note that a function defined by primitive recursive cases from primitive recursive functions is still primitive recursive (rather easy to prove).
So, we attempt to define this by recursion on $n$. Since $\log_b(0)$ is not something we want to consider, we'll assume $b,n > 0$. Let
$\log(b,1) = 0$
Which is certainly primitive recursive. Then define
$\log(b,n+1) = F(\log(b,n),b,n)$
Where $F$ is the following function, defined by cases. $F$ takes $\log(b,n)+1$, and checks if
$b^{(\log(b,n) + 1)} > n+1$
In other words, it sees if $\log(b,n) + 1$ is still shooting too high. If it is, then we stick with what we've got: $\log(b,n)$. Otherwise, the time has finally come to move on up to $\log(b,n) + 1$, and so $F$ outputs that.
It's not hard to see that $F$ is defined by primitive recursive cases from primitive recursive functions, and so have shown that $\log(b,n)$ is primitive recursive.