The definition of shapes you can drop on the page is called a Master. Think of Shapes and Masters as analogous to instantiated objects and classes in OOP. A Visio document has a Masters collection. The masters you look at on the left pane are probably not in the Masters collection of the active document. Each pane on the left is a different document, referred to as a Stencil. Multiple stencils can be opened when you create a new diagram using a template. To learn more about the relationship between Documents, Stencils, Masters and Shapes see Chapter 3 of Developing Microsoft Visio Solutions.
To access one of the open stencils use the Application's Documents collection. You can then get to the individual Masters using the Document's Masters collection. The Master object has a Name and an Icon property. 
There are a number of challenges in using the Icon property in .Net. The Icon property is an IPictureDisp, you will need to find a way of converting this to a image type you can use in .Net. The IPictureDispToImage method in the VB6 library is one way but it only works in 32bit executables. 
The Icon property will throw an COM exception if you callout out of process, i.e. from an external executable as opposed to an add-in. I have never actually used it from C# so I'm not sure if the IPictureDisp property can be marshaled between COM and .Net.
If you can't use the Icon property you could still get the icon by calling the ExportIcon method to write the icon to a file or the clipboard.
The following code shows how get the name of a master and how to export the master icon to a file.
using Visio = Microsoft.Office.Interop.Visio;
...
// Create a new Basic Flowchart diragram ("_U" specifies the US units version).
Visio.Document docDiagram = app.Documents.Add("BASFLO_U.VST");
// Get a reference to the Basic Flowchart Shapes Stencle which was opened by
// the template above.
Visio.Document docStencle = app.Documents["BasFlo_U.vss"];
// Get the Decision master from the Stencil.
Visio.Master master = docStencle.Masters["Decision"];
// Get the name of the Decision master
string masterName = master.Name;
// Export the Icon from the Decision Master. 
// You could use GetTempFileName here.
master.ExportIcon(
    @"c:\temp\icom.bmp", 
    (short) Visio.VisMasterProperties.visIconFormatBMP);