I think there's also a more explicit symmetry-based/~~computational~~ approach (compared to Michael Stoll's linear algebra approach). EDIT 12/13/14: "computational" was the wrong choice of word.

For the $n=1$ (univariate) case this is a problem from (Michael) Artin's *Algebra* previously discussed on MSE here. Given $f,g\in k[T]$, we want a polynomial $P\in k[X,Y]$ such that $P(a,b) = 0$ (here $a,b\in \overline{k}$ are any points in the (infinite) algebraic closure of $k$) if and only if there exists $t\in \overline{k}$ such that $f(t) - a = g(t) - b = 0$. This latter condition is, by the "product of differences of roots" definition of the resultant (which for fixed $a,b$ has $k[a,b]$-coefficients by the fundamental theorem of symmetric polynomials), equivalent to the (formal) vanishing of the resultant of $f(T) - X$ and $g(T) - Y$, which is a polynomial in $k[X,Y]$.

If I'm not mistaken, this should generalize via the multivariate resultant: see Wikipedia or this paper ("Explicit formulas for the multivariate resultant" by Carlos D'Andrea and Alicia Dickenstein).

[BTW, I believe that at least in the univariate case, combining the above with another exercise in Artin shows that if $k = \overline{k}$ is algebraically closed and $f,g$ are not both constant, then (0) the ideal of working polynomials $P$ is principal, and if $m$ is a generator (unique up to scaling), then (1) $m$ is irreducible in $k[X,Y]$; (2) for $(a,b)\in k^2$, we have $m(a,b) = 0$ iff there exists $t\in k$ with $(x(t),y(t)) = (a,b)$; and (3) the resultant is (up to scaling) a power of $m$.

(0,1) can be proven by standard means (e.g. Bezout's identity in the PID $k(Y)[X]$; I'm told this is really a dimension theory argument)---one might only need that $k$ is infinite, not algebraically closed---and (2,3) by looking at the resultant ($k = \overline{k}$ is important here). I don't think Hilbert's nullstellensatz is necessary.]