Back in my Windows days, I used to fully format my PC once a year or so, to start fresh and get rid of some of the slowdowns. It helped.
Would you recommend the same for Macs? What's the recommended way of keeping the computer running smoothly?
I'd say a full format is almost never necessary, though the only thing you'll lose is time.
I've got an OS X install that I've migrated from computer A to computer B to computer C and back to B and upgraded from Tiger to Leopard to Snow Leopard (all upgrade-installs, no reformatting or anything) over the past 6 years and it works great.
Best way to keep it running smoothly is avoiding installing shady software and most of all be very careful if you want to install some cracked stuff.
Keep your hard drive checked and from time to time verify it for errors (Disk utility -> verify) and fix them if needed.
That's what I do to keep my computers (no matter what OS safe).
Just for the statistics for the above method the last 3 OS's I had in chronological order:
You can certainly do so, and it won't do any harm. The question is more of a matter of do you need to? On Windows it's necessary because it doesn't do a great job of keeping your hard disk clean. OS X however is much better at doing so and so it may not really be necessary unless you're experiencing any problems. There's a post on mac.appstorm.net which coveres this nicely.
I'd say yearly is definitely overdoing. Macs don't have a registry, so you don't end up with it getting all krufty.
Since a new Mac OS X version is released every 1.5 - 2 years, I'd say it's not a bad idea to do a clean install and migrate your account from a Time Machine backup each time a new one comes out, or even a more rebuild. That's also a good time to clean out any odd extensions or launch items you added along the way but don't actually use. That's probably worth the effort in better speed and productivity.
For recommended ways of keeping your computer running smoothly, please see my answer to a similar question: "Why is my Macbook Pro getting so slow?"