Master Hendrick Hudson was the first non native to discover the area where Tarrytown and Sleepy Hollow are located, as is noted in the story. Irving also writes about a German doctor who lived there during "the early days of the settlement."
In the first line of the story lies the answer to this question. The town--Greensburgh, "more generally and properly known by the name of Tarry Town (now one word--Tarrytown, New York) lies "the eastern shore of the Hudson, at that broad expansion of the river" and was denominated by the ancient Dutch navigators the Tappan Zee. The name "Tarry Town" comes from the Dutch words for "wheat town" (Terwe Town), since the area's soil was perfect for growing wheat.
The story, however, gives a more entertaining urban legend--appropriate to a story about an area legend, no doubt--about the name of the town. It says the name was given "by the good housewives of the adjacent country, from the inveterate propensity of their husbands to linger about the village tavern on market days."