An $n\times n$ grid has $(n+1)^2$ vertices, each with two degrees of freedom. Since we wish the overall grid to have only $3$ degrees of freedom ($2$ for translation and $1$ for rotation), we need
$$
2(n+1)^2-3
$$
constraints. Each bar provides a one-dimensional constraint, and we start with $2n^2+2n$ bars (two for the bottom and left sides of each of the $n^2$ squares, and $n$ for each of the top and right sides), so the number of additional bars we need is:
$$
b = (2(n+1)^2-3)-(2n^2+2n) = 2n-1
$$
Update
Mike requests a constructive proof in the question, so here's an attempt:
When $n=1$, we can trivially stiffen the grid by stiffening the only square in the grid. Thus, $b(1)=1$.
Take an $n\times n$ grid that is already stiff, and add one row and column to make an $(n+1)\times(n+1)$ grid. The additional row and column can each bend independently of each other. If we stiffen the new corner, we can still bend (as seen in the OP's first diagram). Thus, in order to stiffen the new grid, we must stiffen one square in the new row and one in the new column, increasing $b$ by $2$. Therefore $b(n+1)=b(n)+2$, or equivalently $b(n)=2n-1$.
This proof by induction gives us a general method to construct any minimal stiffening of a grid.
It also leads to a set of rules to determine whether an arbitrary grid is stiff. A stiff grid must have a stiffened square in each row and each column, and every stiff square shares a column or row with another stiff square.