"Cloud computing" is a lot like "Web 2.0" -- it is a buzzword that has an unstable definition and is very, very broad for a professional specialty.
Do you mean "cloud computing" like building web applications which store their data on a server rather than storing it on the client like a traditional desktop app? In that case, build web applications. A short, short list of skills to cover includes HTML, CSS, Javascript, SQL, and your server-side language/framework of choice. I like Rails.
Do you mean "cloud computing" like running massively parallel calculations across a fleet of machines? In that case, Hadoop is a decent place to cut your teeth. (It is much, much easier to play with than things were a few short years ago when then-employer got the "grid computing" bug. The buzzwords change, the buzzwords remain the same...) As for actually having a cloud, well, you don't really need one. A cloud of 1 instance is enough for you to play with the APIs and concepts. Abstracting away the number of instances you have is a major portion of why the techniques work, after all. Alternatively, you can run multiple VMs on one physical machine. (Or, use Amazon or what have you and rent a half-dozen instances for an hour or two at a time.)
Or do you mean "cloud computing" like "on-demand resource scaling"? In that case, I'd pick your favorite vendor (Microsoft is coming out with Azure, Amazon has S3/EC2/etc) and getting familiar with their APIs, limitations, and how you would actually use them to deliver value.
Incidentally, that's the big thing to concentrate on. Toy problems are lovely -- for example, you can calculate solutions to n-queens all day long on your cloud, and that is a good exercise for figuring out the nuts and bolts of how to parallelize a calculation. However, sooner or later you want to be able to do something which actually has value to someone. N-queens does not. You'll find that it is much harder to so something valuable than it is to just run a calculation on a fleet of machines. (There is no push-button API for "do stuff customers find useful", but that is eventually where you want to be.)