Proof that Rel is a Category The Awodey book about Category Theory gives this definition for Rel:

The objects of $\text{Rel}$ are sets, and an arrow $A → B$ is a
  relation from $A$ to $B$, that is, a subset $R ⊆ A×B$. 
The equality relation $ \{ \langle a, a\rangle ∈ A×A\;|\; a ∈ A\}$ is the identity
  arrow on a set $A$. 
Composition in $\text{Rel}$ is to be given by: $$ S ◦ R = \{\langle a, c \rangle ∈ A × C \; |\; ∃b \;(  \langle a, b\rangle ∈ R \; \text{ and }\; \langle b, c\rangle ∈ S) \}$$
for $R ⊆ A × B$ and $S ⊆ B × C$.

How can I actually prove that Rel is a category? 
I'm not really into categories yet but this seem quite obvious since I know a category must have objects (that are the sets, in this case), arrows (relations), identity function (equality relation) and composition of functions (that is the association of relations).
 A: What you've quoted is a definition of all the data needed to have a category: objects, morphisms, identity morphisms, and composition operation.  To verify you have a category you then just have to check that this data satisfies the axioms for a category: that the identity morphisms are actually identities for the composition operation, and that composition is associative.
A: Even though this question was posted quite some time ago I feel like this exercise is very useful for anyone getting into category theory, which is why I provided a solution.
As Eric said, to show that $\mathbf{Rel}$ is a category we need to show that the identity arrows satisfy the identity law and the composition satisfies the associativity law.
Let $f: A \to B$ be a subset $f \subseteq A \times B$, $g: B \to C$ be subset $g \subseteq B \times C$, and $h: C \to D$ be a subset $h \subseteq C \times D$.
To show that $f \circ 1_A = f$, we use the axiom of extensionality (for both are sets).
For the forward direction, let $(a, b) \in f \circ 1_A$. Then we see by definition that there exists some $p$ s.t. $(a, p) \in 1_A$ and $(p, b) \in f$. Since $(a, p) \in 1_A$ implies that $p=a$, we have that $(a, b) \in f$. For the backward direction, let $(a, b) \in f$. Moreover, since $(a, a) \in 1_A$, we have per definition that $(a, b) \in f \circ 1_A$. The argument that $1_B \circ f = f$ is similar.
For the associativity, we want to show that $(h \circ g) \circ f = h \circ (g \circ f)$. We know that
\begin{align*}
(a, d) \in (h \circ g) \circ f &\iff \exists b: (a, b) \in f, (b, d) \in (h \circ g) \\
&\iff \exists b, c: (a, b) \in f, (b, c) \in g, (c, d) \in h \\
&\iff \exists c: (a, c) \in (g \circ f), (c, d) \in h \\
&\iff (a, d) \in h \circ (g \circ f),
\end{align*}
which is what we wanted to show.
