What are the downsides to refinancing?
The downside is you pay closing costs upfront. The interest you save needs to make up for the closing costs within a reasonable time frame (4-5 years is a common rule of thumb). So if you pay $5,000 in closing costs and save $100 a month in interest, in 50 months you'll have made up the closing costs in interest savings.
Are there any pitfalls to watch out for?
Look at the APR of the loan. This tells you the effective interest rate you pay when accounting for closing costs and "points" (prepaid interest in exchange for a lower rate). That's the most effective way to compare mortgages across lenders.
I noticed that some banks offer zero fee refinancing; does this gen mean the total cost of refinancing would be zero, or are there payments that are not typically included in "fees" (closing costs perhaps?)?
This may be how the banks position a loan that has "reverse points" added on. What that means is that you get some cash back at closing in exchange for a higher interest rate. Or, they may increase the principal beyond what you owe now and "cash out" some equity to cover closing costs.
With no points involved, you should expect to pay somewhere between 2 to 5 % in various closing costs, spread across various actual costs (appraisals, title work, etc.) and the bank's "origination fee" (their payment for actually making the loan). As others have noted, it generally takes a drop of about 1% in the interest rate in order to make up for the closing costs in the first 4 or 5 years of the loan. Any longer than that, and you risk moving before your break-even point.
Another way to save interest in the long run is to reduce the tenor of the mortgage from 30 years to 15 years. With a drop in interest rate, your payment may still be affordable, and you'll save much more interest in the long run (as well as a shorter break-even time).