Future road communication scenarios are expected to deploy a radio ad hoc communication technology for the transmission of data between vehicles. Such ad hoc networks are able to support low latencies and cost efficiency, which is very important for, e.g., safety related applications. In addition to vehicle-to-vehicle communication, users also will be interested in accessing Internet services from within the vehicular network. Access can be gained by using roadside installed Internet Gateways, which are able to communicate with the vehicles. However, several difficulties must be addressed in such a scenario. Examples are the interoperability of communication protocol, mobility support, communication efficiency, the discovery of Internet gateways, and the handover of connections from one gateway to the next. In this paper, we are focusing on the aspect of discovering the Internet gateways. We therefore developed a service discovery protocol, which is highly optimized for the characteristics of future vehicular ad hoc networks. Besides the benefit of efficient service discovery, our protocol is able to choose the most suitable Internet gateway among others using fuzzy methods. Furthermore, evaluations show that we are able to decrease the overhead caused by the service discovery process significantly.