I believe that it was leaked recently that the NSA has a long list of zero day exploits on various software "for a rainy day," ie: for whenever it would be useful to them.

The question is, how do they find these zero days? Does someone have to physically sit at a computer and try a whole bunch of random things (ie: remote code execution encoded in base64 inside of a script in a PDF), or are there automated systems which actively pen-test pieces of software for holes where privilege escalation or remote code execution would work?

Zero-days are found in exactly the same ways as any other kind of hole. What makes a security hole a "zero day" relies exclusively on who is aware of the existence of the hole, not on any other technical characteristic.

Holes are found, usually, by inquisitive people who notice a funky behaviour, or imagine a possible bug and then try out to see if the programmer fell for it. For instance, I can imagine that any code which handles string contents and strives to be impervious to case differences (i.e. handles "A" as equivalent to "a") may run into problem when executed on a Turkish computer (because in Turkish language, the lowercase for "I" is "ı", not "i") which can lead to amusing bugs, even security holes (e.g. if some parts of the system checks for string equivalence in a locale-sensitive way, while others do not). Thus, I can try to configure my computer with a Turkish locale, and see if the software I target starts doing weird things (besides talking Turkish).

Part of bug-searching can be automated by trying a lot of "unusual combinations". This is known as fuzzing. It can help as a first step, to find input combinations which trigger crashes; anything which makes the target system crash ought to be investigated, because crashes usually mean memory corruption, and memory corruption can sometimes be abused into nifty things like remote code execution. However, such investigations must still be done by human brains.

(If there was a fully automatic way to detect security holes, then software developers would use it to produce bug-free code.)
