The client-server application paradigm is best understood when cast in the concept of distributed system.
A distributed system is a collection of applications, running on various (possibly heterogeneous) machines, whose distribution is transparent to the user so that the system appears as if running on the user's local machine. This is in contrast to a network, where the user is aware that there are several machines, and their location, storage replication, load balancing and functionality is not transparent.
The expression client-server refers to a software partitioning paradigm in which a distributed system is split between one or more server applications which accept requests, according to some protocol, from (distributed) client applications, asking for information or action. There may be either one centralised server or several distributed ones. This model allows clients and servers to be placed independently on nodes in a network.
Note that this paradigm places clients and servers asymmetrically with respect to each other: servers are there because they offer a certain computational/informational service, and clients make use of it to their advantage. This is in contrast with a peer-to-peer computation/communication model, where all applications in the distributed environment are more or less the same, and use/offer services from/to other ones.
Examples of client-server applications are the name-server/name-resolver relationship in DNS (Domain Name System), the file-server/file-client relationship in NFS (Network File System) and the screen server/client application split in the X Window System.
A server, generally speaking, is a program which provides some service to other (client) programs. The connection between client and server is normally by means of message passing, often over a network, and uses some protocol to encode the client's requests and the server's responses. The server may run continuously (as a daemon), waiting for requests to arrive or it may be invoked by some higher level daemon which controls a number of specific servers (e.g., inetd on Unix).