Faces know which vertices belong to them. So do edges.

By using this fact, you could iterate through edges to find verts that are the interesting ones. Then use these verts to find the faces.

To check which edges belong to each face you could get their verts and then iterate edges and pick ones that have those verts.

One interesting possibility is to construct a data structure that is easy to check out. I did something like that in my FindPoles script (http://blenderartists.org/forum/showthread.php?t=71317). By using vert->edges information, you can iterate through faces to find verts attached to them to find all edges. Then you have to pick the edges that are shared by two vertices. This will give you edges related to each face.