What is it called when an interjection is inserted inside another word?

Solution 1:

Besides tmesis, mentioned by Jon Purdy below, another relevant term is infixation, and fucking here could be called an infix (analogously to prefix, suffix). This specific class of examples is known as expletive infixation.

The exact demarcations of infixation and tmesis, whether they overlap, and whether expletive infixation is actually infixation, seem to be pretty debatable (see comments below). Tmesis is an older term; according to some definitions it includes split phrases as well as words (as in the marvellous West By God Virginia), and may be required to respect morpheme boundaries (so ri-goddamn-diculous would not be an example). Infixation is a more recent term, and is sometimes restricted to cases where the infix is a grammatically significant particle, not an independent word (so expletive infixation would be right out).

Solution 2:

It's called tmesis.