The following script can be used to add a cube and a material to it:
import bpy
bpy.ops.mesh.primitive_cube_add(location=(0,0,0))
obj_matl=bpy.data.materials.new("obj_clr")
obj_matl.diffuse_color=(1,0,0)
mesh=bpy.context.object.data
mesh.materials.append(obj_matl)