Look at the coordinates of $\mathbf{p'}$: the $x$-coordinate is $\cos\theta$, and the $y$-coordinate is $\sin\theta$. Let $O$ be the origin, $P$ the point $(\cos\theta,\sin\theta)$ at the end of the vector $\mathbf{p'}$, and $X$ the point $(\cos\theta,0)$ directly below $P$ on the $x$-axis. If you rotate the triangle $\triangle OPX$ $90^\circ$ counterclockwise about the origin, $O$ stays where it is, $P$ moves to the point $Q$ at the end of the vector $\mathbf{q'}$, and $X$ moves to a point $Y$ on the $y$-axis directly to the left of $Q$. The triangle $\triangle OQY$ is therefore congruent to $OPX$, which means that $|QY|=|PX|$ and $|OY|=|OX|$. Since $Q$ is in the second quadrant, its $x$-coordinate is negative and must therefore be $-|QY|=-|PX|=-\sin\theta$. Its $y$-coordinate, however, is positive, like the $x$-coordinate of $P$, so it’s $|OY|=|OX|=\cos\theta$.
Of course this reasoning applies in this form only when $\theta$ is in the first quadrant. More generally, you’re just adding $\frac{\pi}2$ to $\theta$ when you rotate the vector about the origin, so the coordinates of $Q$ are
$x\text{-coordinate}=\cos\left(\theta+\frac{\pi}2\right)=\cos\theta\cos\frac{\pi}2-\sin\theta\sin\frac{\pi}2=-\sin\theta$
and
$y\text{-coordinate}=\sin\left(\theta+\frac{pi}2\right)=\sin\theta\cos\frac{\pi}2-\cos\theta\sin\frac{\pi}2=\cos\theta\;.$