Today, travel information services are predominantly provided by Global Distribution Systems (GDS), which provide access to real time availability and price information for flights, hotels and car rental companies. However GDSs have legacy architectures with private networks, specialized hardware, and limited speed and search capabilities. Furthermore it is difficult to interoperate them with other systems and data sources. For these reasons, Web service technology is an ideal fit for travel information systems. However to be able to exploit Web services to their full potential, it is necessary to introduce semantics. Without describing the semantics of Web services we are looking for, it is difficult to find them in an automated way. If we cannot describe the service we have, the probability that people will find it in an automated way is low. In this paper, we describe how to deploy semantically enriched travel Web services and how to exploit semantics through Web service registries. We also address the need to use the semantics in discovering both Web services and Web service registries through peer-to-peer technology. This work is being developed within the scope of the IST-1-002104-STP SATINE Project.