It's just virtualisation. You don't need multiple CPUs/cores and a single core is not assigned to each Virtual Machine; the host machine shares its resources with any VMs running at the same time.
Virtual XP Mode is just XP running in an integrated desktop-sharing version of Microsoft's existing virtualisation application Virtual PC. You can certainly run Linux in Virtual PC, though Microsoft doesn't officially support it and it's not as easy to install the ‘guest extensions’ that allow seamless desktop sharing (like in Virtual XP Mode), easy file sharing and faster graphics operations.
You might prefer VirtualBox (open source) or VMware (commercial, but free versions also available), which are essentially the same thing as Virtual PC but do explicitly support Linux. Either way, launching virtualised applications won't be quite as slickly integrated with the host OS as Virtual XP Mode, but it's still very usable.