I think the most effective recognition is sincere appreciation. Whether it's done publicly or privately is not as important as whether you actually mean it. Make sure you do mean it before you open your mouth. And then just tell the truth: that you appreciate what the person has done and what it has meant to the success of the project. It's not rocket science, and it doesn't have to be eloquent. Just say thank you.
One of the key ingredients in expressing sincere appreciation is timing. I prefer to wait for an opportune moment to express my gratitude rather than seeking them out especially for the reason of thanking them. This works only if you have regular interactions with the person. If you don't, you will probably have to arrange something more formal. I like the casual approach because it feels more natural and less awkward. It also helps you avoid the pressure of congratulating them in a public setting, which can be stressful for you and can inspire jealousy in others.
Finally, get a budget for recognition and use it. Words are nice, but T-shirts, mugs, gift certificates, and other swag are better. Put your money where your mouth is.
This was first published in April 2007