Contrary to popular belief, tie-dyeing was not invented in 1960s America. In fact, the answer to this question surely belongs in the category of pre-history, rather than history, as countless dyers through the ages, in many countries, must have experimented with the use of bindings to create patterns on cloth immersed in vats of dye. Different forms of tie-dye have been practiced in India, Japan, and Africa for centuries. The earliest surviving examples, according to the World Shibori Network, include pre-Columbian alpaca, found in Peru, and silk from fourth century Chinese tombs.
Indian & Asian Traditional Textiles Website, Indian Bandhani, one traditional form of tie-dyeing, began some 5000 years ago. This craft was not at first practiced on cotton, as cotton has been used in India for perhaps 3000 years.
Bandhani, also known as Bandhni and Bandhej, is the oldest tie-dye tradition we know that is still practiced. The Malay-Indonesian name for this technique is 'Plangi'. The technique involves a design made of dots, in which many small points are tied with thread before immersion dyeing.
Shibori: Japanese tie-dye (and stitch-dye, fold-dye, and pole wrap-dye)
Japanese tie-dye is included among the many techniques of shibori, which has been used for many centuries to make different types of beautiful patterns on cloth used for elaborate kimonos.
An excellent resource on this subject is Wada, Rice, and Barton's book, Shibori: The Inventive Art of Japanese Shaped Resist.
African Tie Dye
It is well known that tie-dye has traditionally been used in Africa, and there are many modern examples. However, I have never been able to find any reference on the history of this practice, in particular nothing on how long it has been going on.
Modern Multi-Color Tie-Dye
The modern technique of simultaneously applying different colors of dye directly to cotton became possible with the development of cold water fiber reactive dyes, which, though introduced to the textile industry in the 1950s, did not become widely available to the art and craft world until later. The first lucky few in the 1960s used Procion MX dye purchased under the trade name of Fibrec, developed and marketed by the late Mike Flynn in San Francisco (reference: Susan Druding, 1997). Others used duller, inferior dyes, or hazardous naphthol dyes, or acrylic paints.