If in the Odyssey they already washed themselves with warm water prepared on fire, why didn’t the athletes in the loutrons of the palaestrae do the same? They used cold water, which is ineffective for cleaning themselves from the oil and dust.
To answer the question in the title about the earliest bathing in heated water, this almost certainly goes back in some form as long as people could boil water, but there doesn't seem to be a lot of hard evidence before the middle of the first millennium BCE (around 500 BCE).
The Wikipedia page Greek Baths mentions the Greeks had heated baths from the 6th or 5th century BCE, and while its sources aren't very good that time period seems to be agreed upon as when the Greeks had heated baths (they used hot springs before). Ancient Roman bathing on Wikipedia also has some info on Greece.
Baths and Bathing in Ancient Greece, Angelica G. Panayotatou, Proc R Soc Med. 1919; 12(Suppl): 107–121 is an old but authoritative article. It mentions that cold baths were considered by the Greeks to strengthen the body, while hot baths gave tone and vigor (this may have influenced athletes). The oldest mention of heated baths is apparently from the Odyssey, although aside from myth it's not clear when they were used, and historians must rely on pictures on vases as well as archaeological evidence. Herodotus (who wrote in the 5th century BCE) mentions Scythian steam baths (using steam not hot water).
The Development of Bathing Customs in Ancient and Medieval China and the History of the Floriate Clear Palace, Edward H. Schafer, Journal of the American Oriental Society, Vol. 76, No. 2 (Apr. - Jun., 1956), pp. 57-82" offers a brief run-through of bathing habits, noting that steam and sweat baths were common among "primitive" societies for ritual purposes. It mentions that there are records of the Chinese bathing in hot water by the middle of the first millennium BCE, but the lack of literary sources means historians can't tell what they did before then.
Ultimately, since water has been heated for many purposes (cooking, ritual, washing things, as well as bathing), it's hard to tell if people bathed in hot water (and it's particularly hard to know if this was for ritual purposes or for cleanliness) unless you have literary sources describing what was going on. But in situations where water was scarce and it was expensive or difficult to heat what water you had, you wouldn't expect heating water for bathing; the Romans seem to have been the first to build a large-scale infrastructure for it. (It's worth noting that before soap and hot baths, people had other ways of keeping clean - the Greeks used oil in Homeric times and strigils from the late 5th century BCE, and the Romans also used them widely.)