I'm not certain of what you're really trying to ask. Basically, CPU/RAM specifications are usually a function of the chipset more than RAM.
If I have a number of varying
processor specifications (x86, x64,
PII, P4 etc) can I accurately
calculate the memory (speed, size,
etc) that will work with this RAM?
"Accurately calculate"? Um, yes I suppose. The motherboard Chipset and usually the socket of the CPU will determine what specifications of RAM can be supported. For example, some processors are supported by chipset 'X' and 'X' does NOT support DDR3. Guess what? No DDR3 support for that CPU. That's about as simple as it gets. Some CPUs are built around RAM (remember RAMBUS?) while others focus more on what chipset can support which features they want.
Are there any 'gotchas' or can I
deduce this all from specifications
and what properties of the RAM / CPU
should I be checking?
Yes there are some BIG gotchas. People (system builders) typically get hung up on a few details: what CPU can I have - how much RAM can I hold - bus support (PCI-e x16/x8/x4?) and peripherals. The problem in looking at things in this light is that the most important factor is being left out: the chipset.
I don't care how fast a CPU is or what killer RAM you get, the chipset is the heart of the motherboard and in turn, the computer itself. Chipset determines RAM, CPU, buses, everything. So if you want to deduce from specifications of RAM & CPU, start looking at the motherboard chipset.
Another "gotcha" is RAM. RAM can be expensive to rare to find to stable/unstable. RAM is a strange beast. The faster the RAM, usually the slower the timings. If you really want to learn about how RAM works, there are lots of articles all over the web. But learning RAM timing and how the chipset works in conjunction is what really matters.
Don't get swept up in "nehalem" fever or whatever CPU is the flavor of the year. Yeah, it's a solid CPU, but if the RAM is too expensive or flaky and the chipset is 'meh' at best, it's not always worth it. DDR3 is not better simply because of speed. You have to weigh your options carefully with what you're trying to achieve. Are you building a simple computer? Workstation for development or animation/rendering or computation?
And as a last and obvious note, always read the manual before buying anything. You'll save yourself time and money.