The terms "solid" and "liquid"/"fluid" seems date back to Proto-Indoeuropean. Early civilizations worked out metallurgy, the use of snow/ice, and rustic methods of distillation.
During antiquity, many civilization introduced a version of the classical elements. In Europe, Empedocles is often cited as the one having introduced the idea of the four elements: earth, water, air and fire. Aristotle would later expand on Empedocles' theory. These classical elements could be seen as an early version of the states of matter but also as an early periodic table.
Note that Aristotle already speaks of some phase transitions. Regarding vapor (Meteorologica):
I have proved by experiment that salt water evaporated forms fresh, and the vapour does not, when it condenses, condense into sea water again.
The next step in the evolution of the "elements" arrived with the development of alchemy during late Greco-Roman civilization and the Islamic Middle Ages. Geber (Jābir ibn Hayyān) classified matter in terms of four properties: hotness, coldness, dryness, and moistness. European alchemist Paracelsus classified matter in the tria prima: salt (solid), mercury (liquid) and sulfur (flammable). However during this period, many other alchemical elements were proposed, see Wikipedia alchemical symbol for various classifications. These elements go more into the classifications that would result later in the elements of the periodic table and not on the states of matter.
Less esoteric classifications reemerged with the development of chemistry. As others have noted, Jan Baptist van Helmont introduced the concept of "gas" in the 17th century (before that these substances were called "airs" or "vapors"). The study of gases would lead to the gas laws, the ideal gas law and eventually to the atomic theory of gases.
The development of thermodynamics would lead to the discovery of the triple point of water by Lord Kelvin in the 19th century. J. Willard Gibbs would introduce the term "phase". The microscopic understanding of matter in the 20th century, would lead to the precise quantitative understanding of phase transitions (by people like Paul Erenfest or Lev Landau). Irving Langmuir would introduce the concept of plasma in 1928.
At what point between the alchemical elements and modern theory did the concept of "solid, liquid, gas" + "plasma" became the norm is hard to assess and merits more research.