Ask yourself the following questions:
-- Do you really need the real estate? If all you are doing is running your app on a standard Windows or Linux server, it might be ripe to move into the cloud.
--Can you start by migrating your file sharing apps to the cloud? If you are using SharePoint or other "heavy" apps, you might consider using one of the enterprise-grade file sharing services (there are new ones like SpiderOak and Wuala that have better security too).
-- Do you really need to have a local Office suite on your desktop? Google Docs and Microsoft Office 365 both do a decent job of providing the standard word processing et al. services from your browser. You might have to have a chat with your corporate lawyers at this stage and calm them down before proceeding further.
-- Do your users want to use something other than laptops? The more mobile they are, the more it makes sense to move more of their apps into the cloud.
-- What other critical apps or integration touch points can be moved? Here is where the cloud gets trickier: you might not have the right security model, or the interfaces don't work with web apps.
-- Can you transform your data into data as a service. This is really the ultimate destination for the cloud, and it deserves its own q&a.