The Great Other, also known as the Lord of Darkness, the Soul of Ice, and the God of Night and Terror, is the god of darkness, cold, and death in the faith of R'hllor. His true name is never spoken. He is considered the enemy of R'hllor, the Lord of Light.
Followers of R'hllor believe that there are only two gods, R'hllor and the Great Other, who wage an eternal war over the fate of the world. All forces of darkness, cold, and death are believed to be only servants to the Great Other. Melisandre refers to the Others as the "cold children" of the Great Other.  The Great Other has never been mentioned by any Westerosi although all know of the Others from legends. According to Melisandre sleep is a little death, dreams are whisperings of the Other who would drag everyone into his eternal night.
At the Wall, when gazing into the fires, Melisandre sees a wooden face, corpse white, a thousand red eyes, and a boy with a wolf's head beside him. She thinks to herself that they must be the Great Other's champions, as King Stannis is hers. 
Further evidence in the text ties the Last Greenseer, Brynden Rivers, the Old Gods, and Bran Stark to the theme of darkness that draws The Great Other into opposition with R'hllor. The vision of Melisandre pointing towards Bloodraven and Bran as champions of The Great Other is corroborated in this exchange:
There he sat, listening to the hoarse whispers of his teacher. 'Never fear the darkness, Bran.' The lord's words were accompanied by a faint rustling of wood and leaf, a slight twisting of his head. "The strongest trees are rooted in the dark places of the earth. Darkness will be your cloak, your shield, your mother's milk. Darkness will make you strong."