Early definitions
A Dictionary of Slang, Jargon & Cant (1889) by Albert Barrère defines it thus and offers a possible origin:
Canoodle, to (English and Amerito bill can), fondle, pet, dally, and coo.
I meet her in the evening, for she likes to take a walk
At the moment when the moon cavorts above,
And we prattle and canoodle, and of everything we talk.
Except, of course, that naughty topic love.
—Bird o' Freedom.
Possibly from "cannie," gentle.
It may be influenced by the synonym firkytoodle. From the same 1889 dictionary:
Firky toodle (popular), to cuddle or fondle to firk, on the contrary, means to beat, to chastise. In the same way the French caresser, literally to caress, means also to beat.
OED and antedatings
The Oxford English Dictionary defines it:
intr. To indulge in caresses and fondling endearments. Also formerly trans., to persuade by endearments or deception.
The OED has it from 1859, I found a couple of earlier examples. First in a song, "Paddy Loves A Shamrock", published in The Universal Songster, or, Museum of Mirth (1826, 1828, 1829, 1832, 1834, and also in 1830's The Shamrock: A Collection of Irish Songs):

Together, in a lump,
We the universe would thump,
Should they venture to canoodle
Us, every body knows.
The next is in Currer Lyle: Or, The Stage in Romance, and the Stage in Reality by Louise Reeder (1856, 1857):

Oh, you miserable, pettifoggin', canoodlin', deceivin', good-for-nothin' creetur!" shrieked forth Pugs by, as with extended arms she advanced, to fling herself upon his bosom.
This is the former transitive sense as defined in the OED, to persuade by deception. Pettifogging is concerned with legal chicanery and petty quibbling.