Nageshwar is located near Dwaraka in Gujarat, on the way to Beti Dwaraka.  There once lived a rakshasa called Daruka, who was extremely cruel and tortured the good ones.  But yet he was a great devotee of Lord Siva. A Siva devotee, Supriya who was a merchant reached the Darukavanam, where Daruka lived with his wife Daruki, while sailing with his goods.

Daruka asked Supriya to teach him the path of devotion to Siva, the norms of performing pooja and penance.  Fearing that Daruka would use any additional powers gained by such penance, to bad use, Supriya refused to guide him.  The enraged Daruka began to torture Supriya.  Supriya however  was staunch is his faith in the Lord and was unmoved by any torture.  Lord Siva was pleased and appeared and killed the demon Daruka.  Daruki, Daruka's wife, now started giving even more trouble than her husband.  Siva vanquished her too and gives darshan to his devotees at this place as Nageshwar.

The Sivalingam is facing South, with the Gomugam facing East.  There is a story for this position.  A devotee by name Naamdev was singing bhajans in front of the Lord.  Other devotees asked him to stand aside and not hide the Lord.  To this Naamdev asked them to suggest one direction in which the Lord does not exist, so that he can stand there. The enraged devotees carried him and left him on the southside.  To their astonishment, they found that the Linga was now facing South with the Gomugam facing East.
 

There is a contradiction regarding the place, since the Nageswar Jyotirlinga is claimed to exist in two places.  One of course is near Dwaraka and the other is near Audhgram, which can be reached from Purna junction.  And even this is rejected by another claim, which locates it near almora in Uttarpradesh.
This information in italics is from the book "That Lord Siva to be adored" by Prof.K.K.Moorthy