After killing the Anubisath mobs in Ahn'Qiraj and Ruins of Ahn'Qiraj, a Small Obsidian Chunk or Large Obsidian Chunk falls to the ground and is minable. You need 305 mining to mine it. The chunks give obsidian shards, or other gems, and scarabs.
Prior to the Burning Crusade expansion, the mining skill cap was 300. A mining skill of 305 could be obtained by getting the +5 mining enchant. This was often done on a pair of low-quality gloves which are equipped only to mine the ore. A goblin engineer can also make a Goblin Mining Helmet which provides +5 Mining.
With The Burning Crusade, Master Mining is available which increases the maximum skill to 375.