Colored hearing is a form of synesthesia, which (a loose definition) basically means that one’s senses are crossed. It is considered a blessing by those who have it, usually.
One of the more common forms (full-blown synesthetes are about 1 in 25,000) of synesthesia, colored hearing is basically one sees music as well as hears it. Some people see colors, but some people see shapes as well.
I have colored hearing, but I am not a full synesthete. A couple of my friends apparently experience this too, and so I am convinced that it is far more common than typical synesthesia.
What is it like having colored hearing? Major chords are usually whitish or yellowish. Minor chords in many songs appear to be blue or green. Instruments have their own shapes. Violins, cellos, and distorted electric guitars all seem to resemble thick brush strokes, usually brown, black, or red. Harps and pianos are usually whitish spheres, sometimes light blue.
Of course, it changes from person to person, and it depends on the song too. Most people see the colors in front of them, but mine come from my mind’s eye.