Cloud computing is no longer the future but the present. Every day, more and more companies and service providers transfer their businesses and operations to the cloud, benefiting from its multiple advantages. Moreover, the flexibility offered by many cloud services allows to easily build sophisticated services by just composing simpler ones, rather than creating them from zero. Yet, to mitigate potential security threats and keep the maximum performance at any time, a smart selection of those composite services constitutes a key aspect. In this paper, we introduce the reader to the problem of Web service selection based on their reputation scores and subsequently present a survey on some of the most relevant reputation-based Web service orchestration schemes for cloud computing in the literature. For each one of these approaches, a thorough analysis of their pros and cons has been performed, providing a comprehensive comparison amongst all of them leading to the conclusion that, to the best of our knowledge, there is no one single model elegantly fitting to each and every situation that could occur in such a dynamic environment like cloud computing. Finally, we present some current challenges and future research trends in the field of reputation-based service orchestration in cloud computing.