As far as I can remember (and I can't find anything on the internet to refute this), the name "Palpatine" is never used in the original Star Wars trilogy (he's just called "the Emperor"). Despite this, I remember knowing that the Emperor's name was Palpatine long before the release of Episode I, where the name is used. My question is, how did I know Palpatine's name? Was it in the original trilogy somewhere after all? Was the name common knowledge? Any sense of what the original source was?
His name was mentioned in :
Alan Dean Foster's ANH novelization in 1976:
Aided and abetted by restless, power-hungry individuals within the government, and the massive organs of commerce, the ambitious Senator Palpatine caused himself to be elected President of the Republic. He promised to reunite the disaffected among the people and to restore the remembered glory of the Republic. Once secure in office he declared himself Emperor, shutting himself away from the populace. Soon he was controlled by the very assistants and boot-lickers he had appointed to high office, and the cries of the people for justice did not reach his ears (George Lucas [Alan Dean Foster], Star Wars: From the Adventures of Luke Skywalker (paperback; New York: Del Rey, 1976), p. 1, ISBN 0-345-26079-1.)
The Emperor sat, regarding this view, as Vader approached from behind. The Lord of the Sith kneeled and waited. The Emperor let him wait. He perused the vista before him with a sense of glory beyond all reckoning: this was all his. And more glorious still, all his by his own hand.
For it wasn't always so. Back in the days when he was merely Senator Palpatine, the galaxy had been a Republic of stars, cared for and protected by the Jedi Knighthood that had watched over it for centuries. But inevitably it had grown too large - too massive a bureaucracy had been required, over too many years, in order to maintain the Republic. Corruption had set in.
It was also mentioned in 1998 Star Wars Visual Dictionary as per Wookiepedia, but I can't find a cite.
Palpatine was a name that was decided upon and used in the EU a long time ago.
The first name used in early notes is the ridiculous Emperor Ford Xerxes XII, quickly changed to Alexander Xerxes XII, because, as Jar-Jar Binks and "Imperial Centre" (Coruscant) prove, George Lucas is terrible at names.
The name Cos Dashit was also used in early scripts. While The Phantom Menace is the first time Palpatine's name is spoken on-screen, it was first mentioned in the novelisation of A New Hope, and confirmed in the novelisation of Return of the Jedi. Whether this is Palpatine's first or last name has never been established until The Sequel Trilogy, when his first name (Sheev) was revealed, but a popular fan theory at that time was that Palpatine was 'Cosinga Palpatine, Jr,' due to the mention of his hatred for his father and refusal to use "his name," in the book Darth Plageus. His father was Cosinga Palpatine, apparently. I've not read that particular book, and *Wookieepedia's article on Palpatine is, as you will see if you click on my above link, quite large. Skip to "Behind the Scenes" for the information I've provided.
There was still the chance, until Revenge of the Sith aired (or rather, when the novelisation of that film came out, since it came out before the film aired), that Lucas might pull an M. Night Shyamalan out of his hat and make Darth Sidious and Palpatine separate characters, but it didn't seem likely. Revenge of the Sith confirmed what old-school Star Wars fans like you and I had known for decades; that the Emperor's name was Palpatine.
I used to play the Star Wars Customizable Card Game back in 1996 and every card had a little history written on it.
I will not make you go through all of these cards, but this is how I learned about his name. It is written "Emperor Palpatine". As soon as I heard about the Senator Palpatine I automatically made the link.
This said and all of the other answers, there were many ways to get the information about episode 1,2 and 3 before episode 1 came out.
In the late 80's I played West End Games tabletop Star Wars RPG and that clearly stated all the info 'revealed' in the prequels, Palpatine being Emperor, Anakins fall to becoming Darth Vader, etc... All that was New in the prequels was making the Force a disease, and Jar Jar Binks...
The name was first mentioned in the prologue to a novelization of Star Wars and Luke uses the name once in the novelization of Return of the Jedi. So he had his name at least as early as 1976.