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

1$\begingroup$ (I accidentally voted this down, instead of voting it up. If you edit the post, then I can correct my error! Please accept my apologies.) $\endgroup$ – Manny Reyes Jan 17 '12 at 14:50

4$\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$ – Tom Leinster Jan 15 '12 at 23:03

4$\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$ – Tom Leinster Jan 15 '12 at 23:03

3$\begingroup$ A notable exception being 1object categories that are not groups :) $\endgroup$ – Benjamin Steinberg Jan 16 '12 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.