It isn't surprising (that) he should have married her.

that 在这里不可以省略.
that 在定语从句中,除做从句主语外都可省略.
that 在宾语从句中常可省略.
that在同位语从句中不可省略.
再问： 这里是什么从句？
再答： that 引导的主语从句。