There are a lot of options, depending mostly on your totale monthly budget.
We started like you from scratch and it took us about 6 months to get the infrastructure up and running. If you like we could also help you in the whole process, we have a lot of experience.
There are a lot of things to consider when creating a Cloud Offering to your customers, the number 1 question "What exactly do you want to sell?". The reason this question is the most important is because to know what cloud solution would be best for you, you need to know what you want to do with the cloud as each cloud enviroment is not created equally. In the best hosting business you have Cloud Hosting, Cloud VPS, Cloud VM (yes Virtual Machine and Virtual Private Server are separate entities), Email Services, DNS services, etc.
Once you know what you want to do and what your budget is for a solution then you can narrow down the list of Cloud Solutions out there for that best suites your needs and budget, and then from there your enviroment is ready to be physically built to your needs.
Here are some answers to your questions -
> Is there some sort of virtualization that creates cloud hosting?
There are multiple products like VMWare, OnApp, Xen, and even Microsoft is throwing there hat into this arena.
> Do you need a specific operating system in order to support cloud hosting?
Yes and No, depending on the cloud solution you want to use as they all have separate requirements for running.
> How do you link more than one virtual cloud together?
Some clouds may not be able to communicate with one another, the best solution is build a single cloud with a product that can handle all the solutions you want to offer and then just keep expanding the physical servers in the "cluster"
> Can i use multiple virtual servers to create a cloud cluster?
A true cloud will need to be ran on dedicated hardware in order to pass compliance checks as well as ensure a solution that can grow as needed.
Hope this helps, and if you have any more questions feel free to ask!