On June 5, 1999 NASA did indeed release a satellite called Starshine from the Space Shuttle. The satellite is essentially a big ball covered with 900 small mirrors (see this page for a picture). There is also an extremely nice web site that shows you exactly where the satellite is and how to find it in the sky. That web site is here.
If the satellite is at a position in its orbit where you can see it, and if you catch it at the right time, you can see the Starshine satellite with the naked eye. According to this page:
"You, the observer, must be in darkness the satellite must still be in the sunlight and the satellite must be able to reflect enough light to be seen. Starshine will do this with its super reflective mirrors that the students polished. This means that there are two times each day to look for satellites. The first is in the evening when the sky is just dark enough to start seeing stars pop out; this lasts for about an hour after sunset in winter days and up to three hours after sunset in summer."
The page also has a nice illustration of the process.
If you would like to track this satellite, visit the first two links in the list below and then start tracking. NASA even has a way for you to record your observations on its site!