Baking normal map from a cycles shader with normals
An obvious hack which, however, does seem to work well:


Connect the color output of your procedural normal map, that you would normally feed into Normal Map node to Emission node which has Strength set to 1
Connect Emission output of the node to Surface of Material Output
Bake Emit