There are several lines of speculation as to who the Nicolaitans were, but no real evidence. It does seem that they were an early Christian sect, of whom John of Patmos says the Lord disapproved.
H. A. Ironside (http://www.a-voice.org/library/nicolait.htm) says a commonly held view is that they were followers of Nicolaos, mentioned along with Stephen as others as being one of the first deacons appointed to the Church. According to this hypothesis, Nicolaos went his own way, leading a Christian sect given over to false doctrines or immoral behaviour.
G. R. S. Mead, in Did Jesus Live 100 B.C.?, points out that Nicolaos is etymologically equivalent in Greek to Balaam in Hebrew. Revelation 2:14 refers to the doctrine of Balaam just before once again mentioning the doctrine of the Nicolaitans in verse 2:15. The author may see the Nicolaitans as similar to the followers of Balaam, who supposedly allowed their followers to eat food sacrificed to idols. Irenaeus
The second-century Church Father, Irenaeus combines these views in Against Heresies:
The Nicolaitanes are the followers of that Nicolas who was one of the seven first ordained to the diaconate by the apostles. They lead lives of unrestrained indulgence. The character of these men is very plainly pointed out in the Apocalypse of John, as teaching that it is a matter of indifference to practice adultery, and to eat things sacrificed to idols.
If the issue is the eating of food sacrificed to pagan idols, it would seem that Christian doctrine had moved on since the time of the apostle Paul, who expressed indifference to eating food the Corinthians thought might have been sacrificed to pagan idols. In 1 Corinthians 10:27-28, Paul tells them that when offered food they should eat it without enquiring whether it had been sacrificed to idols. Only if their host actually volunteers that the food had been sacrificed to idols should they decline to eat it. The inference Paul makes is that if Christians knowingly eat food sacrificed to idols, they are assenting to the sacrifices, rather than any spiritual concern.
Others have read this as an untranslated Greek word meaning 'rulers over the people,' so that the Nicolaitans were Christian leaders who imposed a hierarchical order in the church and sought to lord it over those below them in the pecking order. If this is the meaning, it foreshadows the actions of the hierarchical Church of later centuries.