In this paper, we recognize the shortcomings of the current search engines that do not index and search the deep Web. We present requirements of a deep Web service search engine, that will lead to the query objects in the deep data sources. In order to realize the DWS search engine, we propose semantic metadata and annotation of deep Web services (DWS), a reasoning component to assess the relevance of DWS for searching the deep Web contents, using likelihood of occurrence of data sources that contain the query terms, and present a method of ranking the DWSs. The deep Web service annotation considers not only the service descriptions like any Web services, but also has the frequency distribution, clustering and semantic prediction functions that may guide the search for DWSs.