This is a comment on Brian's answer, which is however a bit long to fit into the comment box. I wanted to remark that Brian's argument is ulimately not so different from the Noether normalization argument, nor is it so different to the argument linked to here, or to the argument in II.2 of Mumford--Oda using Chevalley's theorem. What they all have in common is the fact that any finite type variety can be projected to affine space with generically finite fibres and big image. On affine space (at least over an infinite field) we can find lots of points, and by the generic finiteness and big image assumptions we can even find such a point lying in the image of the original affine variety with finite fibres. Finding a point on this fibre then involves solving a finite degree polynomial, which we can do over the algebraic closure. Hence our original finite-type variety has a point.
Here is a rewrite of Brian's argument which illustrates this: Following his reduction, we may assume that $k$ is infinite and perfect. We are given a non-zero finite type $k$-algebra $A$, and
we want to show that Spec $A$ has a $\bar{k}$-point, i.e. that we can find a $k$-algebra homomorphism $A \to \bar{k}$. For this, we may as well replace $A$ by a quotient by a maximal ideal, and thus assume that $A$ is a field.
As Brian notes, the theory of finitely generated field extensions allows us to write $A = k(X_1,\ldots,X_d)[t]/f(t)$ (because $k$ is perfect).
We then observe that since $A$ is finite type over $k$, its generators involve only finitely many denominators, as do the coefficients of $f$, and so in fact $A = k[x_1,\ldots,x_d][1/h][t]/f(t)$ for some well-chosen non-zero $h$.
Now because $k$ is infinite, $h$ is not identically zero on $k^n$, and so we are done: we choose a point $c_i$ where $h$ is non-zero, then solve $f(c_1,\ldots,c_n,t) = 0$ in $\bar{k}$.
So one sees that the role of the theory of finitely generated field extensions is simply to provide a weaker version of the Noether normalization, with generic finiteness replacing finiteness. As I already wrote, the other "soft" arguments for the Nullstellensatz proceed along essentially the same lines.