Henriksen tok U. Pihls gymnas, naturfaglinje 1976-1977, Bergen yrkesskole, tømrerlinjen 1977-1978 og avla svennebrev som tømrer i 1981.
Henriksen var ansatt hos byggmester S. H. Pedersen 1978-1981, byggmester Odd Ådnekvam A/S 1982-1985, NOREMA A/S 1985-1986, Bybygg A/S 1986-1987, Fagbygg Vest 1987-1988, Fredskorpset i Kenya for Norad 1988-1990, Bygg og Rehabilitering 1990-1991, Regionalt verneombud Fellesforbundet 1992-1997 og sekretær LO i Bergen og Omland 1997-2005.