Having worked on generating ICC profiles some years back...

First, profiles and calibration are separate things. Calibration means making sure that you get a consistent output for a given input (for output devices) or vice versa for inputs.

There's no point in trying to generate a profile for an inconsistent process. Once you've calibrated it, THEN you can think about profiling it. Note that for output devices, you're really profiling the WHOLE output process - printer, media, inks, enviromental conditions, drying process, etc.

For profiling output devices, professionals use devices called spectrophotometers. These measure the printed output (after it's had time to dry properly) by measuring the reflectance of each patch at many different wavelengths. This lets the device work out an accurate XYZ tristimulus value - basically, an accurate way of measuring what the printed colour looks like under standard illumination.

Then the clever bit takes place - knowing what the printed patches look like, for a given set of input values, the profile generation software can work out what values to feed to the printer to end up with a desired colour.

How many patches you need depends on how good the profile generating software is, and how well it models interactions between different channels.

more patches allow for dumber models, or better information for clever models.