In short, Herodotos most likely learned what he did about 'Aithiopia' from both visiting Egypt, which had a long history of connections with the Greek world by Herodotos' time, as well as from first- and second-hand accounts of Greeks who had interacted with 'Aithiopians', and possibly even from talking to people who he would of thought of as 'Aithiopians'.

The first reference to Aithiopia in Greek literature comes from Homer's Odyssey, which, depending on your reading of the evidence can be read as either a genuine Mycenaean memory, or representative of the eighth or seventh century Greece. I personally lean towards the Homeric epics being representative of the early-seventh century (you can read my understanding of the evidence here, as well as several answers by other contributors). According to Homer, the Aithiopians are 'the most distant of men, who live divided, some at the setting of Hyperion, some at his rising' (Od. 1.23-4, trans. Lattimore), meaning it was believed that the Aithiopians lived the far ends of the earth. Despite these Aithiopians living at the far ends of the earth, Homer's heroes can travel to and from these distant lands. Memnon, who, according to Hesiod, a contemporary of the Homeric epics, is the son of Tithonos and Eos, and king of the Aithiopians (Th. 984-5), is mentioned by Homer (Od. 11.522). Additionally, Menelaos, in recounting his travels after the fall of Troy, says he came to the Aithiopians:

'Much did I suffer and wandered much before bringing all this home in my ships when I came back in the eighth year. I wandered to Cyprus and Phoenicia, to the Egyptians, I reached the Aithiopians, Eremboi, Sidonians, and Libya where the rams grow their horns quickly.'

Od. 4.481-5 (trans. Lattimore)

However, despite these references to Aithiopia and Aithiopians, there is no indication of who these people might be or where they might be in the historical landscape. Mimnermos, writing in the late-seventh century does provide a more specific location for Aithiopia, locating them solely in the east and associating them with the dawn (fr. 12, West), rather than Homer's far west and east locations, but there is still no mention of who they might be. Mimnermos' association might suggest that Greeks were establishing a more specific idea of who the Aithiopians were, but Herodotos, writing in the fifth century, retains the west-east division of Aithiopians (7.69-70). That said, Herodotos does provide a more specific location for the Aithiopians, with some coming from 'south of Egypt' and others being 'assigned to the Indian contingent', with these locations corresponding to west and east Aithiopians respecitvely (7.70, trans. Waterfield). Moreover, Herodotos is even more specific regarding the Aithiopians from 'south of Egypt', saying their capital was the city of Meroe (2.29; for an overview of the Nubian kingdom of Meroe see Shinnie, 1978 and Hakem, 1981). In this same passage, Herodotos claims to have travelled to the island of Elephantine, south of Egypt, and it might have been while he was here that he saw the Aithiopian warriors he describes at 7.69 (although, it is also possible he learned these details from other Greeks). Aeschylos also associates the Aithiopians with the land south of the Nile (Prometheos Bound, 808-9). This all suggests that the Greeks developed a greater understanding of who they thought the Aithiopians were throughout the Archaic period, gradually associating them more and more with the lands south of Egypt, such as Nubia, and of people with a dark complexion, but what caused this specific association?

Despite the sharp break between the palatial civilisation of Bronze Age Greece and the later Greeks, there was only a relatively minor cessation of Greek interactions with the wider Eastern Mediterranean (if there was any cessation at all). Despite contacts between mainland Greece and the Near East being much more common in the post-Bronze Age period than with Egypt, as indicated through the many finds at Lefkandi on Euboia, the foundation of Al Mina on the North Syrian coastline (among other emporia), and the potential Greek raids about Sidon (generally see Luraghi, 2006 and Niemeier, 2001; on the ethnicity of the raiders see Parker, 2000 and Kurht, 2002), there were still relatively early contacts between mainland Greece and Egypt. Boardman provides an overview of a variety of Egyptian finds in mainland Greece from before the mid-seventh century (1999: 112-4), and the story of Kolaios in Herodotos suggests that Greeks regularly traded with Egypt (4.152). Additionally, Egypt occupies a prominent position in the Homeric epics. Menelaos lived among the Egyptians (Od. 4.125-132, 227-8), Odysseus, in his Cretan disguise, tells of raiding on Egypt (Od. 14.257-65, 17.223-43; cf. Hdt. 2.152), and Egyptian Thebes is twice mentioned, and is renowned for its wealth (Il. 9.381-3; Od. 4.125-7). It has been suggested that this reference to Thebes was directly related to the resurgence of Egyptian Thebes' power under the 25th Dynasty, rather than a memory of Bronze Age Greek Thebes (West, 1995: 211). Later in the seventh century, the Saite rulers of Egypt hired Greek mercenaries, alongside Carians, and Herodotos tells us that these Greeks came to Egypt as raiders (Hdt. 2.152). While Herodotos' tale is unlikely to be the whole truth (it is more likely that Greek mercenaries were sent by Gyges of Lydia to Egypt), it is true that Greeks were hired by Egyptians, and we have an inscription by some of these Greek mercenaries, some of whom may have been hereditary mercenaries from Naukratis, the Greek settlement at the mouth of the Nile (ML 7). From the seventh century, there was a permanent Greek presence in Egypt, with many later writers, particularly Herodotos, suggesting a lot of Greek culture, such as the gods, was adopted from Egypt.

Greek presence in Egypt, whether as traders, raiders, or settlers, certainly meant that Greeks were to come into contact with people from the southern Nile valley, such as Nubians living within Egypt. We must also consider the fact that the 25th dynasty of Egypt, the one preceding the dynasty which made use of Greek mercenaries, were Nubian. The Napatan kingdom effectively conquered Egypt during the Third Intermediate Period and installed themselves as Pharoahs, which meant there was likely a greater degree of interaction up and down the Nile which would have facilitated the movement of people in greater numbers (on the Napatan period see Taylor, 2000 and Lloyd, 2000). It is this kingdom that Herodotos mentions in connection with the southern Aithiopians above (the Napatan kingdom was succeeded by the kingdom of Meroe). By travelling to Egypt, or even talking to Greeks who had travelled to Egypt, Herodotos could learn about the southern Aithiopians in particular (the fact that Herodotos has very little to say about the eastern Aithiopians suggests that he simply did not know much about them). There is a similar development in Greek art during the Archaic period, with an Egyptian influence increasingly noticeable as the period goes on (Boardman, 1999; 141-153; see the various figures in this earlier edition of Boardman's here).