How can I write down polynomial relations that define when a polynomial is a square?
Say, for simplicity, you are working over $\mathbb{C}$ or in characteristic zero in general. Then you can guess one of the two values of $g(0)$ (say) and then compute the Taylor series of $\sqrt{f}$. The approach is similar to Hensel lifting: The equation for the first coefficient is non-linear; the equations for the others are all locally linear (so that you get explicit formulas for the coefficients of $g$ in terms of existing data).
I first misread Charles' question, but now that I have it right (I think), here is why I think that the above is still a solution. If you read the coefficients of a polynomial of degree $n$ as projective coordinates, then over $\mathbb{C}$ the set of squares of degree $2n$ is some projective variety $S$ in $\mathbb{C}P^{2n}$. Charles is interested in projective equations for this variety $S$.
For simplicity let's rescale the polynomial $f(x)$ so that $f(0) = 1$. (And I guess we're working the affine chart in which $f(0) \ne 0$ before the rescaling. It shouldn't change things much or at all.) Then you can assume that $g = \sqrt{f}$ also satisfies $g(0) = 1$, and you can make explicit expressions for its Taylor series. Then $g$ is a polynomial of degree $n$ if and only if its Taylor series vanishes in degree $n < k \le 2n$. I think that this gives you the desired equations.
So unless I am misunderstanding the question, temporarily normalize so that the coefficient of $x^6$ in $f$ is 1. One is left with three degrees of freedom, coming from the quadradic, linear and constant terms of the degree 3 polynomial square root.
For concreteness, let $f(x) = x^6 + c_5x^5 + c_4x^4 + c_3x^3 + c_2x^2 + c_1x + c_0$
Then I work out that necessary relations on the coefficients are:
$c_2 = 2(\frac{1}{2}c_5)(\frac{1}{2}c_3-\frac{1}{4}c_4c_5+\frac{1}{16}c_5^3)+(\frac{1}{2}c_4-\frac{1}{8}c_5^2)^2$
$c_1 = 2(\frac{1}{2}c_4-\frac{1}{8}c_5^2)(\frac{1}{2}c_3 - \frac{1}{4}c_4c_5 + \frac{1}{16}c_5^3)$
$c_0 = (\frac{1}{2}c_3 - \frac{1}{4}c_4c_5 + \frac{1}{16}c_5^3)^2$
These are also sufficient since if they hold, then $f$ is the square of $x^3+(\frac{1}{2}c_5)x^2+(\frac{1}{2}c_4-\frac{1}{8}c_5^2)x + (\frac{1}{2}c_3-\frac{1}{4}c_4c_5+\frac{1}{16}c_5^3)$
Unless I did something wrong, it doesn't seem like these computations should be crashing the system. What are you using to run the Groebner calculations?
http://en.wikipedia.org/wiki/Square-free_polynomial gives a method for finding a square-free factorization of a polynomial (over characteristic zero field), ie $f=a_1\cdot a_2^2\cdots a_n^n$ where each $a_i$ is a square-free polynomial. Then $f$ is a perfect square iff $a_{2i+1}=1$ for each $i$.