One of the classes I took last semester covered this... at least the basics.
You first find all possible faults (e.g. a line is stuck at 1, two lines are shorted, etc.), then collapse these down to eliminate things that are functionally the same (an inverter input stuck at one is indistinguishable from its output being stuck at zero). Then you have to come up with a test vector that would have its output affected by a given fault (for the inverter example, the text vector would just be puttying a 0 on the input, and checking the output). Once you have a bunch of vectors, you'll find that many of them cover multiple possible faults, so you can combine them to get the number of required tests down. Then, when you get the manufactured part, you apply the test vector to the inputs, and watch the outputs.
On a circuit as complicated as a processor, it would be impossible to test every part from just the pins, so ALL the latches (or just registers? I'm not sure) in the chip are tied together and can be put into a "scan" mode, which lets you treat them like a giant shift register. This way, you can observe the internal state of the chip at every point. You scan in the values you want, clock the chip, then scan the registers back out and see if they are all correct. This lets you only worry about testing a bunch of circuits the size of the path between registers instead of one gigantic circuit.
edit: To make sure the part works at a given frequency, you run it at that frequency when doing the tests

.