The story
From Californ(ia) + -ication. First use appears c. 1947. Especially popularized by the use as title for a song (1999) and a TV series (2007–2014). Sexual sense either directly from a blend of California + fornication or rebracketing as Cali + fornication.
Etymology from Wiktionary, CC BY-SA 4.0.