You shouldn't (and usually can't) 'paint' heatsinks -- they are made from aluminum and paint doesn't easily stick to aluminum.
Black heat sinks are normally anodized black. This is an electrochemical process that builds a very thin (several micrometers) of aluminum oxide (which is clear). The initial anodization produces a porous surface structure. The part is then dipped in black dye, and then boiling water or steam which causes the porus structure to seal up, sealing in the dye and making the surface permanently black.
The primary reason to anodize is to produce a cosmetically uniform and very abrasion resistant surface. The coating is very thin but very durable and has negligible impact on the thermal conductivity. There will be a slight increase in emissivity, but it is negligible for most heat sinks. Only very hot, very large heatsinks with no forced air and small or no fins will be helped. Basically if you put any effort into improving convection it will be so much more important than radiation it doesn't matter.
Another advantage of anodization is that it can produce a very thin electrically insulating layer. It is possible to use this as the insulation between a heat sink and the tab of a TO-220 transistor. This is generally not done by itself because if you do manage to scratch through the anodization layer you can get a short circuit. If you are careful with manufacturing and test for continuity after you assemble it can be fine, but if you are likely to dismount and remount the transistors it is too risky.
Many aluminum parts are anodized including most heatsinks, and they are often not black. Those shiny 'metalic blue' or similar coatings are also anodization, just with a different dye, and often a thinner oxide layer. If nothing else, people do a clear anodization that leaves the natural aluminum color, but a much thicker oxide layer than the few nanometers that exists natively. This improves scratch resistance and cosmetic uniformity while maintaining the natural appearance.
The reason black bodies are good radiators has to do with what is called the 'principle of detailed balance' which states that the absorptivity of a material is equal to its emissivity. If this were not true, you could put an object with a very high emissivity and low absorptivity next to an object with low emissivity and high absorptivity, and the first one would get cold and the second hot. This would violate the second law of thermodynamics. Anodized aluminum ranges from 'mirror like' to 'grey' in the mid- to far-IR region of interest for thermal radiation of materials at 0-200C.