The trend that the electronic market is taking, aided by the concomitant development of mobile devices, suggests a major change from the way electronic commerce is done today. The increased use of PDAs and laptops requires that ecommerce services and transaction processing facilities need to be accessed from a wireless device. This brings new and challenging research problems into the picture. Discovering services dynamically will become increasingly important in the mobile e-commerce scenario. A service will be selected automatically for a job, taking into consideration its physical location, "context" and other semantic information. To support this scenario, the existing discovery mechanisms need to move beyond trivial attribute or interface matching. They would need to be much more knowledge based. In this paper, we present a summary of the existing service discovery protocols and the work that we have done in the service discovery area in our quest to make service discovery more dynamic.