Well, it is kinda explained on The Daily Beast,
In the book, Ellis Boyd "Red" Redding was a ginger-haired, middle-aged Mick. Harrison Ford, Clint Eastwood and Paul Newman were all considered for the role that went to Morgan Freeman. Darabont alluded to the unusual casting choice by having Red jokingly reply to Andy’s inquiry about his nickname with the line, "Maybe it's because I'm Irish." Happily, they opted to not follow the quote with audio of a studio audience laughing.
Anyway, it was derived from his actual surname of Ellis Boyd Redding, or 'Red' for short, as revealed in his first parole hearing in the film.
Borrowed from comments:
The physical characteristic of red hair is most common in the Irish. And for non-native speakers, "ginger-haired" means "red-haired".
Credits to @G&C, "red-haired" is used to describe orange hair colours because orange is (relatively speaking) the newest colour name in the 7-colour spectrum (besides indigo), so the term "red-hair" literally precedes the use of "orange" as a colour.