You have finished your journey and enter a new world. The intelligent humanoid natives are friendly and speak your language.
However, as you get to know them, you discover that they can't see colour, just black and white.
How can you explain colour to them?
Color: The property possessed by an object of producing different sensations on the eye as a result of the way the object reflects or emits light.
If the humanoid is sufficiently advanced to understand the concept of light as a wave form in the EM spectrum, they may be able to understand it explained as such. If they have tools to measure such phenomena, they will undoubtedly already be associating those values with gradients of their own Grey-scale vision, and therefore can tie the concept of color to these values.
If the humanoid is not so advanced, the best method is likely to refer to objects that they are familiar with and simply point out that while they see it as light-gray the non-natives see it as blue. While they will be physiologically unable to rectify the difference according to their experience of reality, at least they will be made aware of the difference between the two species.
Give them glasses with one eye red and another green, then ask to close one eye and observe and then with another eye - for instance a red object would look different through (to them) magic glasses. Finally try to explain we humans see those two distinct images at the same time and be able to somewhat distinguish them although the sensation is mixed and not really experienced as two different images.
Then follow up with tricolorism and tetracolorism and beyond.
In maths imaginary numbers are often mapped on one axis whilst real numbers are mapped on another. I would try and explain colour in similar terms.
You could also prove the existence of colour by picking two different colours perceived as the same shade of grey and encoding information of some sort with them. This is an effective and simple proof that some visual phenomena is inaccessible to the natives.
Assuming they see greyscale*, I would just show them two objects with the same greyscale shade (i.e. which look identical to them), and explain that to me they look different - my eyes can see things their's can't. I'd explain that in low light my vision is like theirs, but my eyes have something that can see more when the light is brighter.
If they have advanced enough physics to know what wavelengths are, then I would just explain that I can perceive different wavelengths. If they have a sense of hearing and can hear differences in pitch, then I'd explain that brightness is analogous to loudness and color is analogous to pitch - I can see differences in wavelength of light in the same way they can hear differences in wavelength in sound.
If they required proof, I'd do something similar to Dubber Rucky's suggestion. I'd give them two piles of identically shaped pieces of paper which are indistinguishable in greyscale, but of two different colors. I'd tell them to test me; make a shape from the pieces of paper in one pile against a background of pieces of paper from the other pile (which they obviously would be unable to see after construction), and then show it to me and see if I could identify it. They could even have a control group of members of their own species, to prove that it really isn't greyscale-identifiable.
*All of this would work too if they saw pure black and white only and nothing in between
Considering that the natives can see in grayscale, it means that at least they can identify two colors: black and white.
Take a completely black object and ask them what they see it as. Of course they will see they see it as black/dark. Then take a completely white object and repeat the question. They will tell you that it is fully white. Now pick up a red or blue or green object, point to it and tell them that while they see it only as a shade of gray, you can see beyond black and white.
The intelligent folk would easily understand what you mean, but the lesser intelligent would have trouble comprehending the concept.
