For simplicity and definiteness, let's assume that $X$ and $Y$ are smooth and compact (and orientable, which will always be the case if they are complex varieties),
and let $n$ be the dimension of $Y$.
First of all, it might help to note that $H^n(X\otimes Y) \cong H^\*(X)\otimes H^{n-\*}(Y) \cong
Hom(H^\*(Y),H^\*(X))$, where for the final assertion I am using that $Y$ is smooth and compact, so that its cohomology satisfies Poincare duality. Thus if $Z$ is a cycle in $X\otimes Y$,
of dimension equal to that of $X$ (and so of comdimension $n$) it induces a cycle class in $H^n(X\times Y)$, which in turn induces a map from cohomology of $X$ to that of $Y$.
If $f:X\to Y$ and $Z = \Gamma_f$ is the graph of $f$ then this map is just the pull-back of cohomology classes by $f$.

So correspondences in the sense of physical cycles on $X\times Y$ induce correspondences in the sense of cohomology classes on $X\times Y$, which in turn
induce morphisms on cohomology. If you like, you can strengthen the analogy with the $\Gamma_f$ case by thinking of a correspondence as a multi-valued function. Functions induce morphisms on cohomology;
but since cohomology is linear (you can add cohomology classes), correspondences also induce
morphisms on cohomology (you can simply add up the multiples values!). This gives the same construction as
the more formal one given above.

Ben Webster notes in his answer that geometric representation theory provides a ready supply of correspondences. So does the theory of arithmetic lattices in Lie groups and the associated symmetric space. (I am thinking of Hecke correspondences and the resulting action of Hecke operators on cohomology.)

A very general framework, which I think covers both contexts, is as follows: suppose that
a group $G$ acts on a space $X$, and that $H \subset Aut(X)$ is another subgroup commensurable with $G$, i.e. such that $G \cap H$ has finite index in each of $G$ and $H$.

Then (perhaps under some mild assumptions) $(G\cap H)\backslash X \hookrightarrow (G\backslash X \times H\backslash X)
$ is a correspondence (in the physical, geometric sense) which will give a correspondence
in cohomology via its cycle class. The resulting maps on cohomology are (a very general form of) Hecke operators.