How to set grease pencil palette when creating new strokes with python?
A grease pencil object has a list of palettes, each palette has a list of colours. The name of each colour can be used in strokes.new() or be set after creation.

So you can use str = fr.strokes.new(colorname='red') or

str = fr.strokes.new()
str.colorname='red'


An example script that creates a palette and colours -

import bpy

scn = bpy.context.scene

if scn.grease_pencil:
    gp = scn.grease_pencil
else:
    gp = bpy.data.grease_pencil.new('mygp')
    scn.grease_pencil = gp

if gp.layers:
    gpl = gp.layers.active
else:
    gpl = gp.layers.new('gpl', set_active = True )

if gpl.frames:
    fr = gpl.active_frame
else:
    fr = gpl.frames.new(1)

if gp.palettes:
    gp_palette = gp.palettes.active
else:
    gp_palette = gp.palettes.new('mypalette')

if 'red' in gp_palette.colors:
    red_col = gp_palette.colors['red']
else:
    red_col = gp_palette.colors.new()
    red_col.name = 'red'
    red_col.color = (1.0,0.0,0.0)

if 'blue' in gp_palette.colors:
    blue_col = gp_palette.colors['blue']
else:
    blue_col = gp_palette.colors.new()
    blue_col.name = 'blue'
    blue_col.color = (0.0,0.0,1.0)

str = fr.strokes.new(colorname=red_col.name)
str.draw_mode = '3DSPACE'
str.line_width = 3
str.points.add(count=2)
str.points[0].co = (2.0,1.0,0.0)
str.points[1].co = (-2.0,1.0,0.0)

str = fr.strokes.new()
str.draw_mode = '3DSPACE'
str.colorname=blue_col.name
str.line_width = 3
str.points.add(count=2)
str.points[0].co = (2.0,2.0,0.0)
str.points[1].co = (-2.0,2.0,0.0)