Why can you have shiny black objects?

At any surface (at least one which has a different index of refraction from air) some light is reflected, depending on the angle at which the light hits the surface and the polarization of the light; the Fresnel equations will tell you what fraction of your light is reflected and what fraction is transmitted. When you see a black object "shine", you are seeing the reflected light. But since the object is black, all the "transmitted" light is simply absorbed.

The difference between a matte black and a gloss black finish is one of index of refraction, I guess, and possibly of rough/smoothness.

Ptomato's answer is right. I just wanted to add that many glossy black objects in daily life reflect light because they have a thin transparent layer on top. If its index of refraction is high and its surface is smooth, you have a glossy surface. Underneath that, you have your black (and possibly rough) material. This is the case in many cheap plastic objects.