When the 6th day (Shashthee) ends before 1.5 Prahar of night, or 3rd Tithi ends before 1 Prahar of night, it is called Pradosh. 

But generally people observe Pradosh on the 13th day of both Krishn Paksh and Shukla Paksh of a month during Sandhyaa time - up to 1 and 1/2 hours after sunset. The Lord of 13th day is Kaam Dev and the Lord of 14th day is Shiv Jee. The 14th day of Krishn Paksh (dark half) is Shiv Raatri.

Pradosh Vrat Kathaa
The Skand Puran describes a story of a Braahman woman that how Shaandilya Muni prescribed this Vrat to a Braahman woman. She came to the Muni with her two sons Shuchivrat who was of her own, and the other one who was an orphan Prince - Dharmgupt whose father was slain in a battle. Upon the advice of the Rishi the woman and both boys kept the Pradosh Vrat with great devotion. After four months, on the 8th Pradosh, Shuchivrat received a pot of Amrit. He drank it. While Prince Dharmgupt won the hand of a celestial Princess, as ordered by Shiv. He won his enemies and got his lost kingdom back.

Method of Vrat
One should take this Vrat and fast on this day, and keep awake the whole night after the fast is over. Taking bath an hour before sunset, the worshipper should first perform a preliminary worship of Lord Shiv along with Paarvatee, Ganesh, Nandee and Skand. After the worship of Ganesh, Lord Shiv is invoked in the special Kalash placed on a square Mandal with a lotus flower figure drawn in it and spread over with Doorvaa grass. After the formal worship has been completed, a Pradosh story is read and heard by the devotees. This is followed by the recitation of the Maha Mrityunjaya Mantra  108 times. In the end, the sacred Kalash water is partaken of, the sacred ash is applied to the forehead, and the water which was used to bathe the Lord, is drunk. A gift of a pot, a cloth and an image of the Lord Shiv are given to a Braahman to conclude the worship.

Taken from Vishnu Mandir's Web site

Another Description
Once Devtaa and Demons churned the milky ocean with snake Vaasuki as the rope to get nectar to increase their longevity. Not withstanding the pressure, the snake spilled the poison. In order to save everyone, at the behest of Lord Shiv, Nandee and Sundarar brought the poison and Shiv shaped it like a round naval fruit and just swallowed. Now if he swallowed it, the whole life on all the worlds (not only our earth) would be gone, if he didn't, the Devataa and Demons would be gone. So Goddess Paarvatee Jee just held his throat gently and the poison stayed there. Because of this, Shiv felt a little dizzy and rested in the laps of Paarvatee. On waking up, he found that everyone was happy and felt relieved since a big disaster was averted. So, happily, he then began his cosmic dance accompanied by Indra reciting flute, Mahaa Lakshmee singing, Brahmaa Jee playing the Jalaraa, and Mahaa Vishnu playing the Mridang in the presence of all Devtaa and Rishi. This is what is being celebrated as "Pradosh" every fortnight.

Pradosh Worship Procedure:
Pradosh time is between 4:30 PM and 6:30 PM, normally, depends upon the time of sunset because of season and latitude. All the Gods and Goddesses assemble during Pradosh time. So Pradosh worship gives the blessings of all these Gods and Goddesses. We should not go in between Shiv Lingam and Nandee in any temple even in normal time but especially during the Pradosh time, we strictly should not. We should first worship Nandee Jee, then Shiv Jee through the gap in between the two horns of the Nandee. Since Nandee is the one who takes one's prayers to Shiv, we can tell our wishes and prayers in the ears of Nandee. Very sacred to chant Rudra during Pradosh, offer red flower garland and Naivedya to Nandee are very sacred.

Types of Pradosh:
It is believed that each day of the week has different benefits during Pradosh time: