A colloquial version of 'goodbye', now rather archaic.
The British term 'toodle-oo' is a fellow-traveller of various terms associated with walking or departing in a carefree manner - toddle, tootle and their extended forms toddle-off and tootle-pip. Let's also not forget tootle-oo, which is a commonly heard alternative form of toodle-oo, and also its Irish variant tooraloo.
Tootle is a variant of toddle, both meaning 'walk in a leisurely manner'. Toddle, which is really the base word which leads eventually to toodle-oo, is moderately old and makes an appearance in print in Allan Ramsay's The tea-table miscellany, or a collection of Scots songs, 1724:
"Could na my love come todlen hame." [toddling home]
The word is still with us in the term 'toddle off' which, although somewhat archaic in sound, is still commonplace in the UK at least. This was in use by the early 19th century and appears in The Dublin University Magazine, 1838:
"Show this gentleman to his bedchamber, Klaus... and I'll toddle off to my library," said the Nabob.
'Tootle', which also often comes complete with its 'off', has been used to mean 'walk aimlessly' since at least the early 1900s, for example, this piece from the English literary journal The Cornhill Magazine, July 1902:
"I tootled down to Cooney's a half-hour before time."
'Toodle-oo' sounds the kind of language that we might expect P.G. Wodehouse to indulge in, in his Jeeves and Wooster stories. Wodehouse doesn't disappoint and although he didn't originate the phrase his use of it in an early Jeeves story - Jeeves and the Hard-Boiled Egg, 1919, makes a clear link between toddling and toodling:
"Ripping! I'll be toddling up, then. Toodle-oo, Bertie, old man. See you later."
"Pip-pip, Bicky, dear boy."
He trotted off...
The first known record of toodle-oo came just a few years earlier, in a 1907 edition of Punch magazine, which was surely essential reading for the young Pelham Grenville Wodehouse, who was a contributing author to Punch at that date, and so may have written this himself:
"Toodle-oo, old sport." Mr. Punch turned round at the amazing words and gazed at his companion.
The mixing up of all of these terms may also have been influenced by 'toot-toot' and 'pip-pip', which were used in the early 1900s to denote the sounds of early car horns. This has led to tootle-pip and toodle-pip, which might be imagined to be from the same period, but which are in fact late 20th century inventions in the Jeeves style. Wodehouse again had an indirect hand in this, as is shown by this piece from his 1920 novel Damsel in Distress:
"Well, it's worth trying," said Reggie. "I'll give it a whirl. Toodleoo!" "Good-bye." "Pip-pip!" Reggie withdrew.
Tootle-oo is first known from a date that is near enough to that of toodle-oo as to make it difficult to be certain which came first. This variant is recorded in the Letters of T. E. Lawrence (of Arabia), in 1908. The other famous Lawrence, D.H. Lawrence, is coincidentally the first known user of the Irish form tooraloo, also recorded in a letter, this time from 1921, and published in 1968 in Phoenix II:
"So long! See you soon! Too-ra-loo!"
Before closing, I ought to mention another commonly repeated theory on the origin of 'toodle-oo' - that tootle-oo, and by extension toodle-oo and tooraloo, derived as a slang version of the French à tout à l'heure, meaning "I'll see you soon". There's no evidence at all to support this theory, which relies entirely on the co-incidence of sound. There is also some circumstantial evidence against a French origin. Whilst the English and French nobility were closely enough mingled in the Middle Ages for the English then to have taken on many French terms verbatim, by the turn of the 20th century France had long become an unpopular rival. Very few French idioms were granted the status of a popular English slang version in the early 1900s. Just off the top, I can't think of any. It is difficult to imagine a French term being adopted as slang by the hostile and predominantly non-French speaking English populace in 1907.
Finally, I suppose we ought also to deal with another derivation theory from the bottom of the pile, so to speak. This is that the word loo derives from toodle-oo, as 'to the loo'. Let's not waste bandwidth further on that one and just say, "it doesn't".