Further to Alan Storm's recommendations on caching, there's two things I'd specifically recommend you look into related to caching:
- Make sure caching is in memcached, rather than on disk.
I look after a couple of magento installs, and once you get any sort of load on the system, memcached starts to perform much faster. And its dead easy to change it over (relative to doing other magento stuff at least!)
Good starting point is here: http://www.magentocommerce.com/boards/viewthread/12998/P30/ - but if you've not used memcached at all before, its worth looking at some general info about it as well.
- Enable template/view caching.
This is a good article: http://inchoo.net/ecommerce/magento/magento-block-caching/
There are good ones on the magento site too (google magento block caching), but its down at the moment.
To add my two cents to the block caching, I'd advise you create your own blocks in /app/code/local, extending the core ones and defining the cache parameters, name them xxx_Cache and then update your layout to use these blocks instead of the core ones. This way, you avoid losing your changes or breaking the system when you upgrade magento.