The start: We have $\binom{p^2}{2}$ ways to choose $2$ columns of the $p^2.$ So if we select in each row $p$ sq., we will have $p^2$ rows where there each $\binom{p}{2}$ sq, the product of both are equal. Hence we have to divide the $\binom{p^2}{2}$ couples in the $p^2$ rows. (that is the only way, now we have to find such a way yet) The thing is, goes it also for $p>3$ which isn't prime to find a strategy (if yes, there will be a simpler idea then in the other case)

$\binom{p^2}{2} > p^2 \cdot \binom{p}{2}$ for all $p \geq 2$, and other arrangements are possible in principle. (For example, we can actually put 9 squares on a $4 \times 4$ board without creating a rectangle by putting 3 in one row.)

JBL wrote: $\binom{p^2}{2} > p^2 \cdot \binom{p}{2}$ for all $p \geq 2$ OK, made typo in calculus

Here is a construction that does select the same number of squares in each row and column. Think of the selection as a 0-1 matrix. Break the matrix into $p\times p$ submatrices labelled $A_{ij}$ and set $A_{ij}$ to be the permutation matrix corresponding with the permutation $f_{ij}(x) \equiv ix+j \mod{p}$. (When $i=0$, this isn't actually a permutation matrix.) Suppose there is a rectangle of ones in our matrix. Note that it cannot have any vertices in matrix $A_{0j}$ for any $j$. Shoot a ball around the rectangle and keep track of its coordinates modulo $p$. At any time, let $x$ be the coordinate in the axis perpendicular to the direction of motion of the ball. $x$ may only change when we go around a corner. If the corner is in submatrix $A_{ij}$, then the coordinate changes to either $f_{ij}(x)$ or $f_{ij}^{-1}(x)$ depending on the direction from which the ball entered the turn. ($f_{ij}^{-1}$ is well defined since $i\neq 0$.) If the ball turns in submatrices $A_{ij}$, $A_{i'j}$, $A_{ij'}$, and $A_{i'j'}$, then we have for some $x$ that \begin{align*} (f_{ij}\circ f_{ij'}^{-1} \circ f_{i'j'} \circ f_{i'j}^{-1})(x)&=x\\ (f_{i'j'} \circ f_{i'j}^{-1})(x)&=(f_{ij'} \circ f_{ij}^{-1})(x)\\ i'(i'^{-1}x-j)+j'&=i(i^{-1}x-j)+j'\\ i&=i' \end{align*} It follows that the rectangle is degenerate, so our construction works.

Very nice! It does seem natural to ask whether this works for non-primes. (I mean, obviously the very nice construction doesn't work, but maybe something else will.) For example, what about $4^3$ points in a $4^2 \times 4^2$ square? (Maybe a similar construction using the finite field with four elements?) Or $6^3$ points in a $6^2 \times 6^2$ square? It's also not clear that the result is sharp; e.g., for $p = 2$ it is definitely not, and a variation on SCP's combinatorial argument leaves room up to something like $p^3 + \binom{p}{2}$.

The other way to present this construction is the following. We need $p^2$ $p$-element subsets $A_j$ of a set of cardinality $p^2$ such that no two intersect by more than 1 element. If $p$ is the cardinality of a finite field $F$, then the set of all lines in $F^2$ is just what we need, so all powers of primes are fine. The ring structure seems to be of little use but there may be some clever "block construction" that allows one to get products of relatively prime factors.

is there any elementary solution using p'th root of unity?

Here is a very simple construction: Number the rows $0, 1, ..., p^2-1$ from top to bottom, and the columns $0, 1, ..., p^2-1$ from left to right. For $0 \leq a,b,c,d < p$, we select cell $(ap+b, cp+d)$ if and only if $ac+b-d \equiv 0 (\text{mod } p)$. Intuitive explanation of the above method: We divide the columns into $p$ groups (Groups 0, 1, ..., $p-1$), each group having $p$ consecutive columns (numbering from 0 to $p-1$). Now from each row we will select $p$ columns, exactly one from each group in this way: For the row $ap+b$, we select the $b$th column from Group 0, the $b+a$th column from Group 1, the $b+2a$th column from Group 2, and so on until the $b+(p-1)a$th column from Group $p-1$ (when the numbering is always in mod $p$). The reason why this construction works also followed directly from this intuitive explanation