Though I still don't feel fully convinced by it; I don't fully see it. It's entirely possible my obstacle is not so much my skepticism as my stupidity :-)
There seem to be 2 parts to the proof. If you have a list of primes:
You can generate another number from that list
You can always get a prime from that number to add to the list
As for 'stupidity', I wouldn't worry about it. The only people I've ever had call me a moron or question my intelligence in any way have always been people who were less intelligent than I am. And that's not because I'm a genius ;-)
But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (skipping 3).
Now multiply them all to get p. Obviously, p is divisible by all the primes we started with, because we just created it by multiplying them. eg 2 * 5 = 10
Note that p will generally be quite a bit bigger than the primes. Typically, you'll have the primes bunched up near the left of the number line, perhaps with some primes skipped between them, then a big gap to p, and continuing to infinity on the right.
Now we add one to p. This is just to the right of p on the number line. This p+1 is either prime or it isn't.
1. If it's prime, then there is a prime other than the ones we started with. eg 10 + 1 = 11
2. If it's not prime, it has divisors. This proof claims it must include divisors that are prime but are not among those we started with. <-- THIS IS THE BIT I DON'T GET
You can keep doing this, including that new prime (ie either p+1 itself or a prime divisor of it), showing there are infinitely many primes.
So, yes, it's the second part.
This step of the proof invokes the Fundamental Theorem of Arithmetic [0]: the statement that every natural number can be expressed as a unique product of primes (uniqueness isn't the important bit here, just the fact that such a factorization exists).
So you need to accept the Fundamental Theorem of Arithmetic as true before you can fully understand this proof.
[0] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...
So this means: it has a divisor not in the initial primes (actually, I think it must have two). But why should it be prime?
I think a given divisor does not need to be prime; but it must not be divisible by an initial prime. I guess this means that either it itself is prime, or it has divisors which in turn are either prime or have divisors etc. None of these divisors are an initial prime, because then they would also be divisors of p+1, which we have established they are not.
So I guess that's the proof... but I don't feel sure of it. There are too many steps, and I'm not 100% sure of them, and can't see the whole. Perhaps I've not covered some possibility in some step - how could I be sure I've covered them all? Maybe as it becomes more familiar, I will come to see it.