The tickling here isn't the light stroking of the skin - it's the figurative sense of the word that means 'to give pleasure or gratify'. The tickling pink concept is of enjoyment great enough to make the recipient glow with pleasure - (see also in the pink).
That meaning of tickling has found its way into several phrases relating to pleasure, dating back to the early 17th century.
- Samuel Hieron, Works, 1617: "Well might they haue their eares ticled with some pleasing noise."
- Rollin's Ancient History, 1734: "Eating in Egypt was designed not to tickle the palate but to satisfy the cravings of nature."
- Nathaniel Hawthone's Passages from the French and Italian note-books, 1864: "Something that thrilled and tickled my heart with a feeling partly sensuous and partly spiritual."
- St. Nicholas (magazine for boys and girls), 1907: "I'm tickled to death to find some one with what they call human emotions."
and, finally, in 1910, in an Illinois' newspaper - The Daily Review, in a piece titled 'Lauder Tickled at Change', we have:
"Grover Laudermilk was tickled pink over Kinsella's move in buying him from St. Louis."
The inclusion of the term in a newspaper, without any explanation of meaning, indicates that the writer expected readers would already be familiar with it. It seems that that phrase didn't originate much before 1910 though. There are many references to it in print soon after that date, but I can find none earlier.