The suffix -ucus was added to the stem of lactare, just like it happened in caducus from cadere and in manducus from mandere. Fiducia too should come from an unattested *fiducus (thanks @TKR).
According to Ernout (Dictionnaire etymologique de la langue latine) the original word was a feminine adjective, with herba implied. It meant milky grass, and it came from the milky liquid inside. He seems to imply that the suffix should be more or less equivalent to a present participle (lactens, cadens), which makes sense at least looking at their meaning.
Szmerenyi (Greek γἀλα and the Indo-European term for „milk“) says:
Lactuca can hardly be explained as bearing the same relation to lacto as caducus to cado, since lact-are is different from cad-ere; if Ernout is right in regarding late lactare as based on earlier lactans, then at the time of Lucilius or before, when only lactans existed, it was quite impossible to produce a new lactuca on the pattern of cad-ens: cad-ucus. Since, on the other hand, γαλακτουχος is attested in Greek, it is reasonable to infer that lactuca is a Latinization of γαλακτουχη, just as *tartaruca (italian tartaruga) is from Greek tartarouxos.
Leumann (Lateinische Grammatik, vol. 1, par. 304) simply reports the suffix as a "deverbative adjective", because "no big functional group [funktionell bestimmten gruppen] can be found for adjectives and nouns coming from -co- and -quo-". He follows Szemerenyi, KZ 75, 178 (Greek γἀλα and the Indo-European term for „milk“) in saying that lactuca is a substantive coming from Greek γαλακτουχος, which Leumann translates as "containing milk".
Walde (Lateinisches etymologisches Woerterbuch) only says: "from milk, because of the milky juice".