The consensus seems to be that you should accomplish such rotations using quaternions.
See this for the api: http://www.blender.org/documentation/249PythonDoc/Mathutils.Quaternion-class.html
See this for an introduction to the maths: http://en.wikipedia.org/wiki/Rotation_formalisms_in_three_dimensions#Quaternions