The camera uses an RM-1 remote control, which is an infrared device. Note, in my experience, there is some delay in using IR devices between the time the button is pressed, and when the camera finally gets around to taking the picture. It depends on what you are taking pictures of, whether this is a problem.
There is at least one library for controlling cameras with IR controls: http://sebastian.setz.name/arduino/my-libraries/multi-camera-ir-control/
If you don't mind opening up the camera, an alternative way is to add wires to the push button. Obviously, if you do this, you will void a warranty, but in your case, there is no warranty as Olympus warranties generally are for 1 year and only for the original owner (in Europe, Olympus is required to give a second warranty that is transferable, and is longer than the 1 year warranty it offers elsewhere). Just to be cautious, I would put an opto-coupler between the Arduino and the shutter button, so that the camera is not electrically in the circuit with the Arduino (opto-coupler have a LED and light sensor inside the chip, and power on one side turns on the LED, and the light sensor completes the circuit for the other side): http://www.instructables.com/id/Time-Lapse-Photography/step3/Press-my-buttons/
As people have mentioned, you can use a servo to press the button. In this video on making a pole mounted camera, it discusses putting in a servo at about 1 minute, 50 seconds into the video: http://makezine.com/2009/01/14/maker-workshop-pole-camera-on-make/
The Stylus 500 is almost 10 years old (introduced November 29, 2004). Hopefully it is still functioning well for you. I would worry whether batteries still could hold a charge. Compared to other manufacturers, Olympus has a fairly good record of using the same battery for multiple generations, so there was less chance of being stranded because the battery no longer is available. It looks like this battery is still used in current cameras (Olympus TG-850), and you can pick up clone batteries readily. FWIW, I tend to use wasabi clone batteries that bluenook.com sells (http://www.bluenook.com/Wasabi-Power-SP-720UZ-SP-800UZ-SP-810UZ/dp/B0049XIDBW?field_availability=-1&field_browse=2533795011&field_keywords=olympus+li-12b&id=Wasabi+Power+SP-720UZ+SP-800UZ+SP-810UZ&ie=UTF8&refinementHistory=brandtextbin%2Csubjectbin%2Ccolor_map%2Cprice%2Csize_name&searchKeywords=olympus+li-12b&searchNodeID=2533795011&searchPage=1&searchRank=salesrank&searchSize=12). I do have problems with the 3rd party chargers, as they are somewhat fiddily in terms of seating the battery so it charges.
Unfortunately, it uses xD memory cards (common to Olympus cameras of the time). I don't believe the xD memory cards are still being manufactured, but hopefully you can still get them in the used marketplace. If memory, serves there were 3 generations of xD memory cards, and early cameras could not use the 2GB cards. I have gotten rid of my cameras that took xD cards, so I no longer worry about xD.