How to get keyframe data from python? I am looking for help on how to export armatures and their animations in a custom export script.

I wish to have an animation format similar to BVH, i.e. a bunch of [Xposition Yposition Zposition] Xrotation Yrotation Zrotation for each bone for each keyframe.

Given the model (which exports fine using the bvh exporter), how does one get the keyframe data?  A long time searching the object tree of bpy has left me somewhat baffled.
A common way to get the animation data is to loop over the scene's frame range and read the matrices for every single frame. This is okay most of the time, and way easier to do than reading the F-Curve data directly (which won't include F-Curve modifiers and Drivers AFAIK).

Assume the Armature object is currently active:

import bpy

sce = bpy.context.scene
ob = bpy.context.object

for f in range(sce.frame_start, sce.frame_end+1):
    sce.frame_set(f)
    print("Frame %i" % f)

    for pbone in ob.pose.bones:
        print(pbone.name, pbone.matrix) # bone in object space


bpy.types.PoseBone.matrix

You may use the utility function convert_space to avoid fancy matrix math.