Using Alexander duality, you can show that the Klein bottle does not embed in $\mathbb{R}^3$. (See for example Hatcher's book Chapter 3 page 256.) Is there a more elementary proof, that say could be understood by an undergraduate who doesn't know homology yet?
If you are willing to assume that the embedded surface $S$ is polyhedral, you can prove that it is orientable by an elementary argument similar to the proof of polygonal Jordan Theorem. Of course the proof is translation of a homology/transversality/separation argument.
Fix a direction (nonzero vector) which is not parallel to any of the faces. For every point $p$ in the complement of $S$, consider the ray starting at $p$ and goint to the chosen direction. If this ray does not intersect edges of $S$, count the number of intersection points of the ray and the surface. If this number is even, you say that $p$ is black, otherwise $p$ is white. If the ray intersects an edge of $S$, you paint $p$ the same color as some nearby point whose ray does not intersect edges. It is easy to see that the color does not change along any path in the complement of $S$ (it suffices to consider only polygonal paths avoiding points whose rays contain vertices of $S$).
Now take points $p$ and $q$ near the surface such that the segment $pq$ is parallel to the chosen direction. Then they are of different colors. But if the surface is nonorientable, you can go from $p$ to $q$ along a Mobius strip contained in the surface. This contradicts the above fact about paths in the complement of $S$.
Assuming that K is smooth or locally flat, there is a nice geometric reason based on transversality.
The Klein bottle is not orientable. If it embedded in R3 so as to separate a small epsilon neighborhood of its image, then the neighborhood would be homeomorphic to a trivial line bundle over the Klein bottle, K times (1,1), and therefore the neighborhood would also be nonorientable. But since any 3dimensional submanifold of R3 is orientable this cannnot happen.
So the Klein bottle embedding would have to be non separating in this neighborhood. But this means there is a curve C in the neighborhood that intersects the embedded Klein bottle once, transversally.
Now C bounds a disk D in R3 since R3 is simply connected. (Bounding any surface is enough). One can make D transverse to the Klein bottle K, leaving boundary D fixed. One then see that K intersects D in a union of arcs and closed curves, with a single boundary point. But any such collection has an even number of boundary points, a contradiction.
This argument works more generally to show a closed nonorientable surface cannot be embedded in a 3manifold M with H1(M;Z2) = 0.
If you care only about tame embeddings (a figure being tame iff it is homeomorphic to a polygonal or polyhedral figure) then you can prove the nonembeddability by elementary means.
Using the Link appearing theorem:
Any complete 6graph in $\mathbb R^3$ contains a pair of disjoint cycles that forms a nontrivial link.
By splitting the Klein bottle as two Mobius bands identified along their boundary, $M_1,M_2$, note that the meridian of $M_1$ and $\partial M_1=\partial M_2$ will form a nontrivial link and therefore the twocells must intersect.
You can take a look at the article "Why is P2 not embeddable in R3?", by Hiroshi Maehara, American Mathematical monthly.

$\begingroup$ This is very nice, and I read the proofs on Maehara and the Conway and Gordon paper it refers too. So the proof that $P^2$ doesn't embed in $\mathbb{R}^3$ is elementary. So thanks for the reference. However I don't understand your comment "therefore the twocells must intersect". You can isotope the boundary link to something very close to the meridian of $M_2$, but which wraps around it twice. $\endgroup$ – Don Stanley Mar 22 '10 at 13:00

$\begingroup$ This means that the linking number of the meridian of $M_1$ and $\partial M_2$ is twice the linking number with $M_2$. However we know that this linking number is odd by the link appearing theorem. Maybe you had something more elementary in mind? $\endgroup$ – Don Stanley Mar 22 '10 at 13:00
There are proofs that do not use homology, but I don't know that they are more elementary... For example:
Lemma: If S is an embedded compact surface without boundary in an orientable three manifold M then S is orientable if and only if S separates a regular neighborhood.
Thus if K is an embedded Klein bottle in R^3 then K does not separate R^3. Now we have:
Lemma: If S is an embedded compact surface without boundary in R^3 then S separates R^3 into two pieces, one compact and one not compact.
Proof: A cut and paste argument, inducting on the number of saddle points of S with respect to height.//
This is very similar to Alexander's Theorem that spheres in R^3 separate.
If you have a closed (connected) differentiable surface embedded in R^3, then isn't it true that its normal bundle is trivial? This would imply that the surface is orientable. I guess I replied raising another question..

1$\begingroup$ How do you prove the normal bundle is trivial? $\endgroup$ – Don Stanley Mar 22 '10 at 11:14

$\begingroup$ I mean without using some characteristic class theory ... $\endgroup$ – Don Stanley Mar 22 '10 at 11:18

$\begingroup$ I do not know if it is true that the normal bundle of a closed, connected surface in R^3 is trivial. It seems to agree with what Sam Nead says below. I will try to inquiry this! $\endgroup$ – Tommaso Centeleghe Mar 22 '10 at 11:46