I'm not sure what the correct size should be.
Many sites seem to repeat that the apple-touch-icon should be 57x57 pixels but cite a broken link as their source.
Hanselman's and playgroundblues's comments suggest different sizes including 163x163 and 60x60.
Apple's own apple.com icon is 129x129!
See my related question: How do I give my web sites an icon for iPhone?
The official size is 57x57. I would recommend using the exact size simply due to the fact that it takes less memory when loaded (unless Apple caches the scaled representation). With that said, Rex is right that any square size will work
As part of their Safari Web Content Guide, Apple actually has a publicly available page called "Specifying a Webpage Icon for Web Clip" (Javascript required) which covers all of the resolutions and their implementation.
It seems that Apple guidelines as of August 3, 2010 now include the "High resolution" images (for iPhone 4) in their "required" icon sizes.
Looks like we need to provide both a 57x57 and a 114x114 image now, as well as a 640x960 title image.
See Custom Icon and Image Creation Guidelines (Javascript required) which is part of a whole document:
I don't think there is a "correct size". Since the iPhone really is running OSX, the icon rendering system is pretty robust. As long as you give it a high-quality image with the right aspect ratio and a resolution at least as high as the actual output will be, the OS will downscale very cleanly. My site uses a 158x158 and the icon looks pixel-perfect on the iPhone screen.
Updated list October 2014, iOS8
List for iPhone and iPad with and without retina
Update 2014 iOS 8:
For iOS 8 and Iphone 6 plus
Iphone 6 uses the same 120 x 120 px image as iphone 4 and 5 the rest is the same as for iOS 7
Update 2013 iOS7:
For iOS 7 the recommended resolutions changed:
The other resolution are still the same