the preferable tools depend on what you already know, and the details you are looking for.
For example concavity searching ( such as what Fernandez-Recio) point out can be very useful, but that is generally all they do -- be careful some (like Fpocket) are intended to account for where a protein or peptide will fit, others such as ligsite are built with small molecule ligands in mind.
regardless they require a structure, or occasional generate them internally from a sequence
if you have a partner in mind and either structures, or reasonable homology models -- protein protein docking may be of some use.
personally I tend to start with motif searches before I consider the other options (its quick with nice web servers and for a lot of questions it will get you where your going)
--- http://elm.eu.org/ is usually my first (but not only) stop