How to REALLY speed up your Magento site:

The information below on enabling gzip compression will improve your speed a bit, but if you are using a bargain basement web host then that could be a major factor as well. XPC Web Hosting provides advanced technology for speeding up your sites with performance tuned servers in both the USA and Canada. Some of our latest improvements include nginx which speeds up image loading and our database backup system that creates two backups a day and stores off-site archives for 30 days in case of emergency. Learn more.

GZip Compression:
There’s a feature called “gzip” that’s installed by default on most web servers. Modifying your site to make use of it can really speed up the performance.

How much faster?
Try the quick and easy mod_gzip tester by WhatsMyIP.org. Just enter the URL and it will tell you how much faster it would be.

How to enable it for Magento
“One of the drawbacks of Magento is currently its speed if default configuration is used. There are certain ways of making it run faster. The best one is to enable GZip compression by changing .htaccess file a little. You just need to uncomment part of the code. In my case, the speed increase was exactly 235%.

Find the following lines in your Magento .htaccess file and replace them with the following code.

(You just have to uncomment the lines so it looks like the following)

############################################
## enable apache served files compression
## http://developer.yahoo.com/performance/rules.html#gzip

# Insert filter
SetOutputFilter DEFLATE

# Netscape 4.x has some problems…
BrowserMatch ^Mozilla/4 gzip-only-text/html

# Netscape 4.06-4.08 have some more problems
BrowserMatch ^Mozilla/4\.0[678] no-gzip

# MSIE masquerades as Netscape, but it is fine
BrowserMatch \bMSIE !no-gzip !gzip-only-text/html
# Don’t compress images
SetEnvIfNoCase Request_URI \.(?:gif|jpe?g|png)$ no-gzip dont-vary

# Make sure proxies don’t deliver the wrong content
Header append Vary User-Agent env=!dont-vary


Source: inchoo.net

UPDATE: You need to uncomment the following as well:

############################################
## enable resulting html compression

php_flag zlib.output_compression on

Thanks to Reno for pointing this out! It made a huge difference for me!