Selecting a new material slot to selected vertices
One way to do this:

import bpy

mat = bpy.data.materials.new("PinkMaterial")
mat.diffuse_color=((0.8,0.2,0.8))
bpy.context.object.data.materials.append(mat)

for p in bpy.context.object.data.polygons:
    if p.select:
        p.material_index = len(bpy.context.object.material_slots)-1


This would add a pink material to the active object and then go through it's faces to see which ones are selected and then change their material index to the last one. 

There might be more efficient ways to do this as well.