On a couple of sets of fenders I bought it specified on the packaging that your for 25mm tires you should have 35mm fenders, and 35mm tires 45mm fenders. This is a bit overkill, and it looks ridiculous with the 25mm tires. Like FBinNY said, you don't need much. In fact, My 35mm fenders work and look great on the 35mm tires. It's a pretty tight fit, but that helps keep the water spray down.

One other thing about fenders is that the front ones are much more important than you think. Make sure it comes down low enough so that the spray doesn't get at the BB, and hence your feet. Long mudflaps are good for this.