As a central reasoning task in service-oriented architectures, discovery is concerned with detecting Web services that are usable for solving a given request. The emerging concept of Semantic Web services strives towards automation of the complete Web service usage process. Existing approaches for Web service discovery in this field work on confined descriptions of Web services and requests. This limits the achievable accuracy of discovery results. Exploiting the full potential of semantically enabled Web service discovery, this paper presents a discovery framework that works on sufficiently rich descriptions of the functionality provided by Web services and requested by clients in a state-based model of the world. We differentiate two elements for formally specifying requests for Web services: goal templates as generic objective descriptions and goal instances that denote concrete requests by instantiating a goal template. Upon this, we specify a two-step discovery procedure along with semantic matchmaking techniques that allow to accurately determine the usability of a Web service. The presented framework is defined in a language independent manner so that it is applicable to several languages for semantically describing Web services.