What is the difference between PXE and Wake-on-LAN (WoL)?

You cannot compare them like that. WoL is used to power on and PXE is used for booting (to load an OS from a remote server), so WoL happens before PXE.

Wake On LAN (WoL):
Wake On LAN (WoL) is a feature that allows a computer to be powered on. Computers that are "powered off" might actually use up a little bit of electricity, and be able to perform some very minor functions. As I recall, older computers would sometimes use a separate (set of) wire(s) that connected to the network card. These might have been made for providing some tiny amount of power or data communication. It may seem like the computer is using no electricity because it is quiet because no fans are being used, but a tiny amount of electricity can be made available for some of the cards.

If the network card was using Wake On LAN, then it would check incoming Ethernet frames for a particular pattern. If that pattern was seen, then WoL would send a message to the system (perhaps to the intelligent ATX power supply, or the motherboard's WoL pins?) to have the system "wake up" more fully. The system would then power on. Once the computer powers on, the computer will do what the computer always does whenever it powers on: the computer will boot.

To make all that happen, you need another computer on the network to send a magic Wake-on-LAN frame that will be recognized by the computer that supports WoL.

Pre-eXecution Environment (PXE):
PXE (which I have heard pronounced as "PiXiE", by multiple people) is related to how the computer boots. Instead of booting from code on the hard drive, or booting code from a CD, the PXE process can be what is used for booting up the computer. This process searches a network for code to boot. If the PXE client (which is commonly built into the circuitry/chips on the computer that is booting) can locate a PXE server, then the PXE client will download code from the PXE server. After downloading code from the PXE server, the PXE client will run that code. The entire PXE process may use some other protocols, like DHCP and TFTP.

Contrasting WoL and PXE:
With WoL, the computer then boots up normally. "Normally" might involve PXE, or it might not. The BIOS might just boot straight to the hard drive. So, WoL and PXE don't have to be related at all. WoL just means "power on". What does the computer do when it powers on? It boots. WoL "wakes" the computer up, and that's all WoL does. Using WoL does not mean that PXE will be used.

PXE affects how the computer boots. PXE can be used when the system boots up with WoL, or when the system turns on because someone pressed the power button to turn on the computer, or possibly because software told the computer to perform a "cold"-style (full) restart. So, using PXE does not imply that WoL was used to turn the system on.

You could use WoL and then PXE, so both are used. Or just one could be used. They don't do the same thing. They are both related to the overall gigantic process of a system starting, and both involve network cards, but the similarities basically end there. They aren't really related to each other.

OS Requirements (WoL):
Regarding the other question: Yes. WoL is generally OS-agnostic, because no operating system is running, because the much of the computer is powered off. (Generally including fans, and I presume that the CPU and main system RAM might also be lacking power. That would prevent an operating system from being active.)

OS Requirements (PXE):
When I've typically seen the option to use PXE, that option was built into the BIOS. I presume that add-on cards can use PXE when the BIOS checks if any add-on cards have an "option ROM" (similar to how an add-on card which is a RAID controller can allow the user to enter a RAID management tool before any operating system is loaded from a disk). PXE can download an operating system; you can even have the server provide different boot images so that the computer can download a different operating system each time it boots. The operating system that PXE boots up will be whatever code is on the image that gets downloaded.

Note that some operating systems might work better with PXE than others. They may support being able to start up with a minimal amount of data, and then use the network to locate even more data. Other operating systems may be based on a design that might expect to see all of the critical data sitting on a physical disk. So, different operating systems may support the PXE experience with different degrees of ease. Before dedicate yourself to a specific idea that relies on PXE to start up a specific operating system, take a moment to read about how easy it is to use that operating system with PXE. Enough people have enjoyed dabbling with PXE that such information is probably relatively easy to find.