Separation of 2 compounds ( Powder )
Your question is about as broad as chemistry itself. Like you said, you may try dissolving them in water, if one is soluble and the other is not. If it's not working with water, chances are it will work with ethanol, or acetone, or... see, there are many solvents on the shelf. No luck? Maybe by now you've found something that dissolves them both, so you may try fractional crystallization. Still no luck? Maybe the compounds differ in density or selective adhesion of something, so flotation might help. Still no luck? Chromatography, by any chance? No? Distillation, like you said (provided they both would survive until boiling point), or maybe sublimation (good for $\ce{NH4Cl + NaCl}$)? No? Well, there is a multitude of chemical processes; some of them might change (that is, destroy) one compound or both, but probably in such a way that they can be regenerated later.

And if everything else fails, you can always look at the mixture under a microscope and separate the crystals manually.