import Blender
       from Blender import Scene, Object, Camera
       #
       camdata = Camera.New('persp')           # create new camera data
       camdata.name = 'newCam'
       camdata.lens = 16.0
       scene = Scene.New('NewScene')           # create a new scene
       scene.objects.new(camdata,'Camera')     # add a new object to the scene with newly-created data
       scene.makeCurrent()                     # make this the current scene

Warning:

scene.objects.new is the preferred way to add new objects to a scene. The older way is to create an object with Object.New(), link the data to the new object, then link the object to the scene. This way is not recommended since a forgotten step or run-time error in the script can cause bad things to be done to Blender's database.

If you use this older method, it's recommended to always perform the operations in this order. This is because if there is no object data linked to an object ob, scene.link(ob) will automatically create the missing data. This is OK on its own, but if after that object ob is linked to obdata, the automatically created one will be discarded -- as expected -- but will stay in Blender's memory space until the program is exited, since Blender doesn't really get rid of most kinds of data. So first linking ObData to object, then object to scene is a tiny tiny bit faster than the other way around and also saves some realtime memory (if many objects are created from scripts, the savings become important).