First, of course make sure APC is installed. On Debian or a Debian-derived system (like Ubuntu), you can do this with sudo apt-get install php-apc. Once you’ve got APC installed and working, add the following snippet to app/etc/local.xml under your Magento site, in between the <global> and </global> tags:
<global> ... <cache> <backend>apc</backend> <prefix>SOMETHINGUNIQUE_</prefix> </cache> ... </global>
“SOMETHINGUNIQUE” should be just what it says – something unique to the site you’re caching. This is a prefix that lets the webserver figure out what bits of cache go with what sites; so if you’ve got two different sites running, both with the same APC prefix set, you will have serious problems later. I recommend using your domain name, without the periods – so if your site is mystore.com, your prefix would be MYSTORE_ in the snippet above.
Make sure cache is enabled under System/Cache Management, and refresh it. You’re done.