I resist asking questions until that feeling starts to kick where there has to be a fast but illusive answer. I want to see blender.stackexchange progress out of beta, it has been pretty useful already!
import bpy, bmesh
obj = bpy.context.object
bm = bmesh.from_edit_mesh(obj.data)
bm.verts.new((2.0, 2.0, 2.0))
bm.verts.new((-2.0, 2.0, 2.0))
bm.verts.new((-2.0, -2.0, 2.0))
bm.faces.new((bm.verts[i] for i in range(-3,0)))
bm.verts.new((2.0, 2.0, -2.0))
bm.verts.new((-2.0, 2.0, -2.0))
bm.verts.new((-2.0, -2.0, -2.0))
bm.verts.new((2.0, -2.0, -2.0))
bm.faces.new((bm.verts[i] for i in range(-4,0)))
# update, while in edit mode
# thanks to ideasman42 for making this clear
# http://blender.stackexchange.com/questions/414/
bmesh.update_edit_mesh(obj.data)
Adding edges is also similar
# let's add two verts and connect them as an edge
bm.verts.new((0.0, 1.0, 1.0))
bm.verts.new((0.0, 0.0, 1.0))
bm.edges.new((bm.verts[-2], bm.verts[-1]))
# remember to do a bmesh.update_edit_mesh(obj.data)