The combination of virtual server technology and the Infrastructure-as-a-Service (IaaS) approach to utility computing promises to revolutionize the way in which distributed software services are deployed. Server virtualization technology can be used to capture complete reusable software stacks, shifting the complexity of middleware installation and configuration from deployment to packaging. IaaS clouds provide a set of interfaces for controlling virtual machines and configuring their hardware and network environment, substantially reducing the complexity of service provisioning. In this paper we identify and tackle a few of the remaining challenges in fulfilling the promise of radical simplification of distributed software service composition and deployment. We propose an approach and architecture for composition and deployment of virtual software services in cloud environments. We introduce a virtual appliance model which treats virtual images as building blocks for composite solutions. Virtual appliances use a port abstraction to negotiate their communication parameters. A solution architect creates a virtual solution model by composing virtual appliances and defining requirements on the environment in a cloud-independent manner. The virtual solution model is transformed to a cloud-specific virtual solution deployment model used to generate a parameterized deployment plan that can be executed by an unskilled user. We validated our approach through a prototype implementation demonstrating flexible composition and automated deployment in our local lab virtualization infrastructure and in Amazon EC2.