The icon should be a 57x57 pixel PNG. The PNGs generated by Apple have a PPI of 72.01 so I guess something in that range will work fine. Don't have a very high PPI else images are not rendered properly.
If you want to use a custom icon and not let the iPhone to apply the gloss to your icon, add a key to info.plist called UIPrerenderedIcon (is a boolean value) and make it checked.
When submitting the app to the app store, you will need a 512x512 pixel version of your app's icon (this one in jpeg or tiff format) and at least one screenshot of your app. You can have additional 4 screenshots of the app.
EDIT
Now the specs for icon (to be submitted in iTunes connect) and the app icons have changed. The icon to be submitted to itunesconnect must be 1024x1024 px.
For the app icons, you can find details here - http://developer.apple.com/library/ios/#documentation/iPhone/Conceptual/iPhoneOSProgrammingGuide/App-RelatedResources/App-RelatedResources.html#//apple_ref/doc/uid/TP40007072-CH6-SW1
Also, make sure the icon files are NON-INTERLACED PNG files. Recently one of our apps' binary was marked invalid since one of the app icon files was an interlaced PNG.