VMs can definitely cross over. Usually you have them networked, so any malware with a network component (i.e. worms) will propagate to wherever their addressing/routing allows them to. Regular viruses tend to only operate in usermode, so while they couldn't communicate overtly, they could still set up a covert channel. If you are sharing CPUs, a busy process on one VM can effectively communicate state to another VM (that's your prototypical timing covert channel). Storage covert channel would be a bit harder as the virtual disks tend to have a hard limit on them, so unless you have a system that can over-commit disk space, it should not be an issue.
The most interesting approach to securing VMs is called the Separation Kernel. It's a result of John Rushby's 1981 paper which basically states that in order to have VMs isolated in a manner that could be equivalent to physical separation, the computer must export its resources to specific VMs in a way where at no point any resource that can store state is shared between VMs. This has deep consequences, as it requires the underlying computer architecture to be designed in a way in which this can be carried out in a non-bypassable manner.
30yrs after this paper, we finally have few products that claim to do it. x86 isn't the greatest platform for it, as there are many instructions that cannot be virtualized, to fully support the 'no sharing' idea. It is also not very practical for common systems, as to have four VMs, you'd need four harddrives hanging off four disk controllers, four video cards, four USB controllers with four mice, etc..
2020 update: all the recent hardware based vulnerabilities (Meltdown,Spectre,Foreshadow,ZombieLoad,CacheOut,SPOILER,etc) family of vulnerabilities are great examples of how VM's are always going to be able to communicate, simply because they share hardware (caches, TLB, branch prediction, TSX, SGX) that were never intended or prepared to be partitioned and isolated.