Horn is slang for the male erection, based on its shape - and horny is a derivative of that.
The OED has this definition for the slang sense of horn:
An erect penis; an erection. Also in phr. to have (also get) the horn: to be sexually excited. (Not in polite use.)
The earliest two citations in the OED are:
1785 F. Grose Classical Dict. Vulgar Tongue Horn Cholick, a temporary priapism.
1879–80 Pearl (1970) 257 A man with light trousers, of decency shorn, Stop and talk to young ladies while having the horn.
According to the OED, horny originally meant "consisting of horn" (citations from 1398 onwards), later "Callous or hardened so as to be horn-like in texture" (1693). Then in 1889 it was first attested with this meaning:
Sexually excited; lecherous. (Chiefly used of a man.) Cf. horn n. 5c. slang.
(Horn 5c is the definition of horn that I've cited above.)
Green's Dictionary of Slang gives the following etymology for horn:
[resemblance to an SE horn]
(where SE means "standard English" according to his list of abbreviations).
And for "horny", his etymology simply refers us back to that definition of "horn" and hence that etymology.