An API is not necessarily web-based. It's really just a specification of how to talk to someone else's work using a programming language. A web service, on the other hand, is one example of someone else's work which a program will talk to using an API.
In the case of a web service, an API might specify how to communicate over the web to the service, in order to use it. Frequently, however, the communication protocol for a service will not be described directly. Instead, the API will be a specification of how to use a client library provided by the service author. A good example of both of these is the Google Maps API. Google provides both a specification of how to request data from their service via HTTP (a web service API) and a client library in Javascript which can be used to request the same thing.
But this is not the only possible use of the term API. jQuery (which is a Javascript library, but not a remote web service) also refers to its documentation as API Documentation. Similarly, the Wikipedia page on API gives the example of the POSIX standard for operating systems.
In short, an API is a specification, while a web service is one example of a system which can be documented with an API.