As many as you like, if you don't mind overcommitting the cores. CPUs overcommit quite well - it's when you start overcommitting RAM that you get into trouble.

But surely you'll have a hell of a lot less CPU power than, say, 128 of Linode's 512mb virtual servers, meaning they would have much worse performance if fully used?

That would depend on the type of CPU Linode is using. What the CPU's frequency is, the amount of cores, whether it has or does not have hyper-threading technology.

The hyper-threading technology is a pretty cheap way to add more virtual cores to your VPS's which is great. One thing is for sure and that is that Linode provides you 4 virtual cores and not 12 per VPS. But, that of course doesn't mean their CPU is better or worse. But, if you can run 6 cores at 3.8ghz, or 12 cores at 1.9ghz then I wouldn't worry too much about not having enough CPU power for your virtual private servers.

If any CPU-overcommitted VM system has guests which all want 100% of the CPU, they'll all suffer. No two ways about that. I don't know what hardware Linode put their 512MB instances on, and I don't know their overcommit ratio. 128 is more guests than I'd put on a 64GB host, though.

If your typical load is actually at 100% CPU for the majority of the time, I'll go out on a limb and suggest that VPS might not be the best bet anyway.