How to add a Texture to a Material using Python?
Similar to material_slot.material, there is a texture_slot.texture

(I'm assuming Blender internal from the texture_slots.add in q)

mat = bpy.data.materials['Material']
tex = bpy.data.textures.new("SomeName", 'IMAGE')
slot = mat.texture_slots.add()
slot.texture = tex


A simple example using Cycles can be found here https://blender.stackexchange.com/a/14115/15543