Does a match that is deposited into a non-qualified deferred compensation plan need to be taxed for FICA purposes? If so, how would it work if there was a graded vesting schedule?

The contribution (match) to an account balance is included as taxable wages for FICA purposes under the special timing rule under Code Section 3121 (v) when the principal no longer is subject to a "substantial risk of fordeiture" (i.e., becomes vested). Earnings (or interest) becomes subject to FICA in the year that the principal amount of contributions on which those earnings (or interest) have accrued becomes subject to FICA.