Suppose we have two categories such that presheaves on them are equivalent. What can be said in this situation?
4 Answers

7$\begingroup$ In a sense there's nothing to add to Finn's answer: it's a necessary and sufficient condition. But I'll add something anyway, in case the nLab page seems too daunting. Given maps p: A > B and i: B > A in a category such that pi = 1, the map ip is idempotent. An idempotent is said to be "split" if it is of this form. A category is said to be "Cauchy complete" if all idempotents in it are split. You can always Cauchycomplete a category, by throwing in a splitting for each idempotent. $\endgroup$ Commented Jan 15, 2012 at 23:03

6$\begingroup$ In practice, most commonlyencountered categories are already Cauchy complete. For example, any category with finite limits or with finite colimits is Cauchy complete. For such categories, Cauchycompletion does nothing, so the categories of presheaves on them are equivalent if and only if they themselves are equivalent. $\endgroup$ Commented Jan 15, 2012 at 23:03

3$\begingroup$ A notable exception being 1object categories that are not groups :) $\endgroup$ Commented Jan 16, 2012 at 4:26
Finn's answer, as expanded by Tom, is great. However, since the question is so broad ("what can be said?") let me point out that there is a different thing that can also be said. If $C$ and $D$ have equivalent categories of presheaves, then $C$ and $D$ are equivalent objects in the bicategory of profunctors. In other words, there are profunctors $C \to D$ and $D\to C$ whose composites in either direction are naturally isomorphic to identities. This is also a necessary and sufficient condition.
Both Finn's and my answer generalize to enriched categories and enriched presheaves; the only difference is that the notion of "Cauchy completion" is different. In general, it means completion under all absolute colimits.
Let $k$ be a field. If $A$ and $B$ are (small) $k$linear categories with $K$linearly equivalent categories of $k$linear functors to $k$vector spaces, then $A$ can be obtained from $B$ by a sequence of "contractions and expansions» from $B$. See Theorem 4.7 in this paper by Claude Cibils and Andrea Solotar.
In short: it happens exactly when there is a bigger category and disjoint full embeddings of the two categories $\mathcal A,\mathcal B$ into it, such that every arrow is a composition of arrows of the form $a\to b$ or $b\to a$.
It's easy to see that the EilenbergWatts theorem holds for monoid actions, moreover, it also holds for categories, presheaves and profunctors in place of rings, modules and bimodules:
Theorem.
Let $\mathcal A$ and $\mathcal B$ be categories, and $F:\mathcal{Set}^{\mathcal A}\to\mathcal{Set}^{\mathcal B}$ has a right adjoint, then there is a profunctor $U:\mathcal A\not\to\mathcal B$, such that $F\simeq (H\mapsto H\otimes_{\mathcal A}U)$.
In other words, in the realm of modules (even over categories), the only adjunctions are the tensorhom adjunctions.
[As a note, $U$ can be obtained from $F$ by setting $U(a,b)=F(\hom_{\mathcal A}(a,))\,(b)\ $.]
If $F$ is an equivalence of categories, then its inverse $G$ is both its left and right adjoint, so by the above theorem, $F\simeq(\otimes U)$ and $G\simeq(\otimes V)$ for some profunctors $U:\mathcal A\not\to\mathcal B$ and $V:\mathcal B\not\to\mathcal A$.
And, by $F$ and $G$ being inverses to each other, we obtain $U\otimes V\simeq \hom_{\mathcal A}$ and $V\otimes U\simeq\hom_{\mathcal B}$, as the hom functors are the identites for profunctor composition $\otimes$, meaning that $U$ and $V$ form an equivalence in the bicategory of categories and profunctors.
As for such, there exist an adjoint equivalence with arrows $U$ and $V$ in $\mathcal{Prof}$, that is, profunctor isomorphisms $\eta:\hom_{\mathcal A}\to U\otimes V$ and $\varepsilon:V\otimes U\to\hom_{\mathcal B}$ satisfying the zigzag identities.
Writing up these identities for the inverse of $\eta$, we receive a structure called Morita context:
$$ 1_U\otimes\varepsilon=\eta^{1}\otimes 1_U \quad
\text{ and }\quad\varepsilon\otimes 1_V=1_V\otimes\eta^{1}\quad\ (*)\,,$$
which can be very neatly interpreted as follows:
First, the elements of the sets $U(a,b)$ for a profunctor $U:\mathcal A^{op}\times\mathcal B\to\mathcal{Set}$ can be regarded as heteromorphisms $a\to b$ which we can add to the disjoint union $\mathcal A+\mathcal B$, and their compositions is described by the action of $U$ on the morphisms.
Thus, we obtain a bigger category $\mathcal U$ containing both $\mathcal A$ and $\mathcal B$ and no arrows of the form $b\to a$.
Composition ($\otimes$) of profunctors can be viewed as having formal compositions $\langle u,v\rangle$ of these heteromorphisms $u\in U(a,b),\ v\in V(b,a')$, quotienting out by $\langle u\beta,\,v\rangle\sim\langle u,\,\beta v\rangle$ for arrows $\beta\in\mathcal B$.
Thus, the above maps $\varepsilon:U\otimes V\to\hom_{\mathcal A}$ and $\eta^{1}:V\otimes U\to\hom_{\mathcal B}$ extend the composition operations to $\mathcal U\cup\mathcal V$, assigning certain arrow $a\to a'\,\in\mathcal A$ to every $\langle u,v\rangle\in(U\otimes V)(a,a')$ and similarly for compositions $b\to b'$ in $\mathcal B$, and the above two equations $(*)$ state exactly the altogether associativity of these operations.
In other words, we obtain a bigger category, which is called a bridge $\mathcal A\rightleftharpoons\mathcal B$, that is a category containing $\mathcal A$ and $\mathcal B$ as disjoint full subcategories and no more objects (thus, it is a symmetric version of a profunctor, in a sense).
One direction of my initial statement then follows, since the composition maps $\varepsilon$ and $\eta^{1}$ are in particular surjective.
For the other direction, their surjectivity in the presence of equations $(*)$ implies invertibility.
If $\mathcal M:\mathcal A\rightleftharpoons\mathcal B$ is a bridge with surjective zigzag compositions, then in particular, for every object $a\in Ob\mathcal A$, its identity $1_a$ also factors as $uv$ for some $u:a\to b,\ v:b\to a,\ b\in Ob\mathcal B$, but then $vu:b\to b$ is an idempotent,
so if we take the idempotent completion $\mathcal M^{id}$ of $\mathcal M$, that will be a bridge $\mathcal A^{id}\rightleftharpoons\mathcal B^{id}$, in which every object of $\mathcal A$, and thus also each of its idempotents, is isomorphic to some object of $\mathcal B^{id}$ and viceversa.
The existence of such a bridge $\mathcal C\rightleftharpoons\mathcal D$ is actually equivalent to the equivalence of $\mathcal C$ and $\mathcal D$ (at least in the presence of choice): fixing isomorphism for each $a$ yields an equivalence functor $\mathcal C\to\mathcal D$, and the other direction can be proved by a similar argument as above.
So we obtain that $\mathcal A^{id}\simeq\mathcal B^{id}$.
For more on the subject, refer to this paper.