There are multiple metrics to use when determining when to add cores to a VM. Core usage, as you mentioned, is one of the most obvious metrics. Others include actual core performance and multi-threading capability of the applications.
A CPU can be a performance bottleneck without ever going above 10% usage. Usually this is the case when your CPU is just plain slow (1ghz vs 2.5ghz), and you'll want to upgrade your underlying host hardware. (My 1.5ghz tablet is painfully slow, even though CPU usage never rises above 10%. It's just a slow CPU!)
There are still a lot of applications out there that are not multi-threaded, so no matter how many CPUs (cores) you throw at them they will never use more than one. Usually in this case you'll want to investigate upgrading your application to take advantage of multiple CPUs before you add more to the VM. Also, some operating systems have restrictions as well (usually based on licensing); for example, Windows Server 2003 Standard only supports 4 physical CPUs, but doesn't care about cores per CPU. This can affect whether you add virtual CPUs or cores-per-vCPU to a VM.
Assuming that my host resource usage is minimal, I would add cores to a VM when my performance metrics show an average (mean) CPU usage greater than 50% during regular business hours. It's an arbitrary number, and depending on your applications and usage patterns you may want more cores at 25% or 75% mean CPU usage, though by the time your mean hits 75% it's probably way past time to make any changes. You'll want to pay attention to consistent usage vs usage spikes. If your CPU is normally at 5% but spikes to 100% every few minutes, you don't want to add cores until you've determined the cause of the spikes. FYI, vSphere has these performance metrics built in.
EDITORIAL NOTE: This is probably most appropriate to an application that has a fairly constant load, such as a web server. Applications with a hit-and-miss load, such as a dev server that compiles code for 20 minutes every 4 hours, would be very different. In that case you would look at the performance of the application (the compiler) and the peak CPU usage when that application is running (compiling). 100% CPU during the entire compiling operation would probably benefit from more CPU, as long as the compiler is multi-threaded. But then, you have to worry about your devs getting mad at you for cutting their play time in half.
Some applications, such as MS SQL Server and MS Exchange, will intentionally hog your resources (memory is the most noticeable one) and this is by design, so you need to be aware of what your applications are supposed to be doing. You need to weigh the actual application performance against its resource usage - if SQL server is using 100% CPU and responding quickly, that's different from a SQL server using 100% CPU and responding slowly.
If application performance is slow, but your metrics and benchmarks reveal that your CPU is not the bottleneck, then don't worry about adding cores - though, if downtime and host resources are no concern, then temporarily adding cores to prove a point to your users doesn't take anything but 10 minutes worth of time.
Also, keep in mind that a good hypervisor, like VMWare ESXi, allows you to over-provision. That means you can provision 4 VMs with 4 cores each (16 cores total) even though your host only has 8 cores. The hypervisor dynamically allocates host resources to the VM that needs them the most, so with 3 idle VMs your 4th VM can chew on as much of your host as you can allocate to it. The catch you want to watch out for is licensing, as some applications are licensed per core or per CPU and not per machine or OS installation.