As @nightcracker explains, fully homomorphic encryption (FHE) is one possible solution (though not practical). There are others, some of which are practical.
Multiparty computation is another possible solution. The tradeoff here is that MPC typically requires more communication than FHE, but the result is that it can be practical for many situations. The Might Be Evil framework would be a good one if you only have 2 parties. VIFF is good for multiple (more than 2) parties. The SPDZ protocol (of which I don't believe there is a publicly available implementation) is a recent protocol that is very efficient. It uses FHE for the preprocessing phase, so that part might not be super practical on computationally challenged devices.
MPC and FHE are both general solutions to the problem. In many instances there might be a specialized protocol that would be better. An example of this is searching on encrypted data, which relates to the example you gave.
