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:
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!