Yes black has the highest emissivity (it also absorbs radiation best- reciprocity - or Kirchoff's law of thermal radiation). Note that it has to be "black" at the relevant wavelengths, which do not necessarily correspond to being black in the visible spectrum.
That means that radiative heat transfer will be maximized if the emissivity approaches 1 (black body). If your heat sink "sees" mostly cooler things it will have better cooling, and if it sees hotter things it will not cool as well.
However, radiative heat transfer is typically not all that significant compared to conducted heat transfer and (usually most important for semiconductor heat sinks in normal environments) convection heat transfer. So usually the color is not all that important compared to the fluid dynamics design of how air flows over the fins and how the heat is conducted to the fins. The fins mostly "see" other fins, so radiation has even less of an effect.
Exceptions exist for those of us designing electronics that has to survive in a vacuum and/or in space or very high altitudes, and if the item being heat sinked (or what it sees) is very hot, radiation can become more important (4th power of temperature).
An example situation where a shiny (low emissivity) heat sink could be superior would be a voltage regulator heatsink in direct view of a heater, incandescent lamp, or vacuum tube.
Any color of dye you like can be applied when anodizing, or none at all, which is called "clear" anodize. Normally the oxidized aluminum (it's not a coating) is a quite thin insulating layer, but in some cases it can be made more than a few mils thick.
Edit: Let's do a back-of-the envelope calculation to see how significant radiation is. I'll assume a model 530002B02500G heatsink from Aavid Thermalloy. It has a natural convection rating of 2.6 degrees C per watt, which I believe is rated at a rise of 70 degrees C over ambient.
So if your ambient temperature is 25 degrees C and the heat sink is at 95 degrees C the total power dissipated will be 27W.
How much of that is due to radiation? We can treat the heat sink (for radiative coupling purposes only*) as a block of dimensions 64mm x 25mm x 42mm (ignoring the notch) which represents a surface area of 0.011 square meters.
Heat loss due to radiation (assuming emissivity of 1) is
\$ q = \sigma A (T_H^4 - T_C^4)\$, where \$\sigma\$ is the Stefan-Boltzmann constant ~5.7E-8 (and the temperatures are in Kelvin)
Substituting in the values we get a heat flow of 6.4W due to radiation at 95 degrees C heatsink temperature and 25 degrees C ambient, so less than 25% is due to radiation under optimal conditions for maximizing radiation loss. More likely we've got some forced convection going on and the radiation heat loss is less again. A heat sink that is closer to a cube would have less heat loss due to radiation as well. Not quite low enough to be ignored, but not dominant.
- For radiation, the convolutions of the heat sink "see" other heat sink surfaces mostly so a block of the outer dimensions is correct for radiation (to a first approximation). They actually have an effect in making the effective emissivity closer to 1.0 than the surface itself since some of the light that is not absorbed will bounce into other surfaces and get another chance to be absorbed (and the same in reverse, of course for radiation of heat- but it's easier to imagine the absorbing of light because we can see visible light and cannot see the IR wavelengths that the heat sink is emitting at reasonable temperatures - if your heat sink is glowing red, yellow or blue-white you probably have other problems).