The answer is: It depends!
There are two common definitions of positive semidefiniteness.
Definition 1: $\newcommand{\m}{\mathbf}\newcommand{\A}{\m A}\newcommand{\B}{\m B}\newcommand{\x}{\m x} \A \in M_n(\mathbb R)$ is positive semidefinite if and only if for all $\x \in \mathbb R^n$ we have $\x^T \A \x \geq 0$.
Definition 2: Same as Definition 1, with the additional requirement that $\A$ be symmetric.
Let's start with the second definition, which may be the more commonly assumed. In this case, the stated result is true and follows easily from the definitions. In particular,
$$
\x^T(\A + \B)\x = \x^T \A \x + \x^T \B \x \geq 0 \>,
$$
since both terms in the middle are nonnegative. Furthermore if $\A$ and $\B$ are both symmetric, then so is $\A + \B$. Hence,
$$
\x^T (\A + \B)^2 \x = \x^T (\A+\B)^T (\A+\B) \x = \|(\A+\B) \x\|_2^2 \geq 0 \>.
$$
Now, let's look at the first definition. If we drop the assumption that $\A$ and $\B$ are symmetric, then the stated result in the question is false.
It is, of course, still true that $\A+\B$ is positive semidefinite (the same proof above applies), but $(\A+\B)^2$ may not be.
Counterexample: It suffices to consider only a single matrix $\A$, with $\B = 0$. Take
$$\A = \left(\begin{array}{rr} 1 & -2 \\ 0 & 1\end{array}\right) \>.$$
Then, if $\x = (x_i)$,
$$
\x^T \A \x = x_1^2 - 2 x_1 x_2 + x_2^2 = (x_1 - x_2)^2 \geq 0 \>.
$$
So, $\A$ is positive semidefinite. However,
$$
\A^2 = \left(\begin{array}{rr} 1 & -4 \\ 0 & 1\end{array}\right) \>,
$$
which is clearly not positive semidefinite; to see this, just take $\x$ to be a vector of ones.
Best Answer
Because $A$ is PSD, we have $v^\top A v \ge 0$ for any vector $v \in \mathbb{R}^n$. In particular, if $v$ has zeros in all entries except $v_i$ and $v_j$ in entries $i$ and $j$, then $0 \le v^\top A v = \begin{bmatrix}v_i & v_j \end{bmatrix} \begin{bmatrix}A_{ii} & A_{ij} \\ A_{ji} & A_{jj}\end{bmatrix} \begin{bmatrix}v_i \\ v_j \end{bmatrix}$ which shows that $\begin{bmatrix}A_{ii} & A_{ij} \\ A_{ji} & A_{jj}\end{bmatrix}$ is also PSD, and must have a nonnegative determinant. [This is Brian Borchers's hint.]