How many particles are necessary to observe a well-defined state of matter?
Computationally:

It depends on the material but in general $10^2 - 10^4$ atoms/molecules is a representative range. I learned this concept as the thermodynamic limit; i.e. the number of particles in a system at which increasing particle number does not change density significantly. For obvious reasons it's also called the macroscopic limit. In Statistical Mechanics we bridge the gap between small "countable" systems and macroscopic "mole-quantity" systems with the thermodynamic limit.  

Our lab develops and applies models for small molecules like $\ce{H2, CO2}$, noble gases, hydrocarbons etc. for use in computer simulation. The usual method is to parametrize a model such that phase transitions (i.e. density changes as a function of temperature or pressure) are accurately mapped, and intermolecular potentials are comparable to highly accurate QM calculations (CCS(D/T/Q) methods).

One can reproduce accurate phase diagrams of noble gases using just 40-100 atoms by putting the system in a fluctuating periodic box and changing particle positions until an energy minimum is reached (the computational method is called Monte Carlo) under given $T$ and $p$ -- this is called the isothermal-isobaric ensemble, or $NPT$. You can achieve identical results using the $\mu VT$ (grand-canonical ensemble) wherein chemical potential, volume, and temperature are fixed, but $N$ is allowed to change. For professional model development it is more common to use $10^3 - 10^4$ particles for a good fit.

Below is a snapshot of output from a Monte Carlo program obtaining the density of $\ce{He}$ at STP using 100 atoms (the reported value is 0.1786g/L). You can see that $\ce{He}$ in this model is a near-ideal gas with compressibility factor $Z \approx 1$ :


I think the answer is more appropriately expressed via computational (Statistical-Mechanical) methods because the concept of the thermodynamic limit arose in and is used by SM. In general, the central-limit theorem is where the concept came from, which states that fluctuations to the mean of a quantity (density here, $N/V$) are expressed as $\frac{1}{\sqrt{N}}$, thus for $N=10,000$, the mean density can expectedly vary by $0.01$. For $N=N_A$, the variance would be certainly negligible.