2 Maneras:
Usando el Xvid4PSP (mi preferido, con distintos perfiles, calidad, compresión, etc). Te deja seleccionar qeu subitulo quieres, y posteriormente se convierte, ya sea a MP4 (de PSP) o PMP (para el PMPadvance)
ó
Usando el PMP advance, que dejaba poner subitutlos, solo poniendolo al lado del video con el mismo nombre (creo). No hace falta codificar de nuevo, y se puede usar tanto en MP4 y o PMP (la ultima version tenia MKV, pero la PSP no aguanta mucha resolución)