Essentially, a continuous process of trying to find the purest forms of different materials, and then find patterns and distinctions in how they behave.
For example: say you pick up a random rock. You can try to measure as many qualities as possible about it: colour, hardness, density, magnetic susceptibility, and so on. Then, try to make it into something else. Heat it, freeze it, attack it with acids, water, alkali, and see if it seems to behave like anything you already know about, or whether you can convert it into something that does.
The more methods you have, the more sure you can be that two different objects are composed of the same material, or different materials. Particular similarities can cause problems, for example it took a long time for people to manage to separate the lanthanides because they behave very similarly under many tests.
In some cases, elements have also discovered after finding unexpected results -- for example, helium was discovered in the spectral lines of the sun's radiation before it was ever isolated or identified on Earth.
It's a common problem of trying to find the irreducible complexity behind an opaque emergent system -- in this case, trying to work back from the materials we have to their fundamental components. The more information you have, the easier it is to discern more elemental qualities and patterns, and the more other bits you can find.