Old English starian "to stare, gaze, look fixedly at," from Proto-Germanic *staren "be rigid" (source also of Old Norse stara, Middle Low German and Middle Dutch staren, Old High German staren, German starren "to stare at;" German starren "to stiffen," starr "stiff;" Old Norse storr "proud;" Old High German storren "to stand out, project;" Gothic andstaurran "to be obstinate"), from PIE root *ster- (1) "stiff."
Not originally implying rudeness. To stare (someone) down is from 1848. Related: Stared; staring.