I've only had terrible experiences with W3 Total Cache, for all of my 4 WP sites: it went from taking a site down completely to returning 404 errors on all pages except for the homepage, as some rewriting rules went berserk. Uninstalling it is also slightly troublesome, as it tends to leave a stuffy .htaccess that you will need to clean yourself. As many others have pointed out, W3 Total Cache appears to be overkill for a normal WP installation.
WP Super Cache, on the other hand, works like a charm and is much easier to work with, even for someone who isn't very knowledgeable about how caching works. Word of advice: although I have successfully used mod_rewrite caching with WP Super Cache and it's definitely the fastest, I noticed it did incur quite some load. I then changed it to php caching and the server load went down to half. Depending what your priorities are, you might want to opt for php caching - it's only marginally slower than mod_rewrite but more efficient load-wise.