The system of CAs with the root-CAs and their subordinate CAs are IMHO in principle akin to the system of banks with their main sites and subsidiries. In the case of banks, a customer of a bank commonly has trust for that bank but not necessarily trust for the other banks of the world. Anything from the other banks can thus be trustworthy for him only through an corresponding action of his bank that provides him the required trust. This implies that the root-CAs must somehow manange to trust one another in order that certificates from the region of one root-CA could be used in the region of other root-CAs. How is that trust among the root-CAs actually being established in practice?
Root CA don't trust each other and don't actually talk to each other. Each root CA lives in its own world, alone. Root CA don't trust anybody; it goes the other way round. That's also where the bank analogy breaks down: banks have to talk to each other, while root CA totally ignore each other.
You (or your OS or browser) trusts one or several root CA for asserting things about identities and public keys. The various roots don't have to assume or even be aware that you are trusting several of them simultaneously. It is your problem, not theirs. In practice, your OS or browser vendor has chosen for you that you will trust about one hundred root CA, which you can see by inspecting your browser configuration menus.
Cross-trust between CA is a rare event, which typically happens in the wild as an aftermath of mergers: two businesses, each with its own internal CA, decide to fuse into a single entity. But deployed desktop systems in what formerly was business A only trust rootA, while deployed systems from business B only trust rootB. The ideal solution would be to modify all systems so that they all trust both rootA and rootB, but that's hard work (depending on how computers are managed in the organization, they may have to send sysadmins in front of each of the thousands of PC, to do the few needed operations) and it may take time. So, in the meantime, something can be done at the CA level: make rootA emit a certificate (an intermediate CA certificate) for rootB (and vice-versa). This means that rootA asserts that whoever trust rootA may also trust that which comes from rootB (and vice-versa).
Some people have invested a lot of thought into coming up with terminology for the various cases of cross-trust; see RFC 5217 for (a lot of) details. However, I insist, this does not happen often in the "real world".
This implies that the root-CAs must somehow manange to trust one another
That is not how trust works in the X.509 model at all.
A user trusts many root CAs directly, through their client's SSL settings. Each root operates independently - they do not trust each other.
If you go to site-A.com and your browser doesn't trust any root or intermediary CA on its certificate chain, you are out of luck. There is no mechanism to take someone else's word for it.
(There are other models based on multiple notaries or webs of trust, but X.509 is mostly where we are today.)
As the other answers have mentioned, Root CAs aren't obliged to trust each other. That is considered "your" responsibility*.
But there is also currently a fundamental technical constraint, even if we or they wanted to establish Root CA cross-verification: X509 certificates don't allow for multiply-rooted signature trust chains.
So you can't get a certificate signed by multiple elsewise disparate Root CAs; you are forced to pick one and only one Root CA like a rabbit out of a hat. Which is in part why the browser and operating system vendors put so many Root CAs in the hat; with little or no earnest attempt to check for rabies.
At best, if everyone wanted to do this** with existing version 3 of X.509 they would have to treat all certificate permutations of
A -> B -> C -> ... -> Z as equivalent, to get a multi-root signature of
* Well, not your's but your browser and operating system vendor's responsibility at any rate. I hope you trust those vendors.
** The Root CA providers don't want to do this. It would undermine both their business model and oligopoly.
For SSL, the user trusts the browser manufacturer, because there are lots of CAs listed as trusted per default. A security-aware user would remove all root CAs and just add those that he personally trusts.
For Windows, the CAs are stored in the "trusted root authorities" which means that any certificate issued by any of these CAs (for code signing or whatever) can be trusted. So the same applies there too.
The CA system means that the user has to trust some CA that they only issue certificates to people that really are who they say they are (or whatever the certificate says). So from then on you can establish a secure connection or know the code was really signed by that person.