Your 3 basic choices when looking for black sand are:
Black Beauty - It's coal slag with the possibility of other stuff being mixed in. It's questionable from a safety standpoint and this topic has been covered several other times in the past. If you do a search for "black beauty" you can find some good threads about this. It's upside is that it's cheap. I've personally never seen it for sale around here, but I've also never looked for it.
Tahitian Moon Sand - It's really expensive, usually about $1/lb. I've found it to be widely available, I saw some at Petsmart. Based on photos that I've seen, it seems to have fairly large grain size and is somewhere between a large sand and a small gravel. It also appears fairly irregular in shape/size, maybe a little sharp. Here's a photo I found online.
3M Colorquartz - It's middle of the road. I paid $50 for 100 pounds of this. I've found it to be fairly available, but you have to check 3M's website to find a retailer. It's available in 2 grades, T-Grade, which is larger and more irregular/pointy, and S-Grade which is small and very round, good for fish that like to dig or spit sand. It's a nightmare to clean(from my experience) but well worth my stained bath tub. I think it's the best looking substrate I've seen so far and my fish love it. Here are some of my shots of the substrate.