Olympia is a very bicycle-friendly town, as far as American towns go. Very few roads have a speed limit over 25 or 30 mph, and many arterial roads have bike lanes.
Trails
Chehalis Trail: This amazing bicycle trail runs through Lacey and the east side of Olympia and spans 22 miles from Woodard Bay to the Yelm to Tenino trail near Rainier. The trails make for an outstanding collection of cycling pathways covering the far South Sound, typically available all year-round and with minimal interference from car traffic.
Bicycle Shops
Bike Tech: Bicycle shop located in East Olympia near Ralph's Thriftway.
Falcone Schwinn: BIcycle shop located in West Oly on Harrison.
Joyride Bicycle: Located just outside of Olympia in Lacey.
Old Town Bicycle: Located on Capital Way in downtown Olympia.
OlyBikes: On State Avenue near the Transit Station down town.
Bicycle Powered Delivery
Star Courier: Star Courier is Olympia's pedal powered delivery service.
Resources
The Thurston Regional Planning Council has a neat map where you can plan a biking route here or you can pick one up at the library or City Hall.
Google Maps has a bicycle trail layer that's incredibly useful if you have a mobile device with an Internet connection.