One of the keys to making a proof accessible to high school students (or just non-mathematicians) is to make the answer relevant. This gives a dual responsibility, to ensure that the theorem is motivated and that the proof is accessible. The proof of the infinity of the primes has been mentioned already and is a fantastic example. You can lead students in to it using the (almost trivial) proof that there is no largest integer.
Another example is the classification of the regular polyhedra. With good students and models you can even lead them to the proof there there are at most 6 regular polytopes in 4d (actually showing they all exist is a little harder).
Keeping with polyhedra, the Euler characteristic is also powerful. Start with balloons and get the students to draw lines freely so you get a tiling. Then get them to count faces, vertices and edges. David Eppstein collected 19 proofs to choose from, several of which would be perfect for non-mathematicians: http://www.ics.uci.edu/~eppstein/junkyard/euler/
As a final example (and to show that it does not have to be deep mathematics to motivate) you can consider the question of blocking a square on a chess board and filling the remainder with tromioes. It starts with a puzzle, you can get people to play with, and leads to a lovely induction proof: http://www.cut-the-knot.org/Curriculum/Games/TriggTromino.shtml
Actually polyominoes are a fantastic source of many other fun, non-trivial but accessible proofs.
