If you want to replace an Application icon (e.g. when using Wineskin to run Windows-applications), you can do so by replacing the icon file inside an app, located at:

AppName.app/Contents/Resources/AppName.icns

However, sometimes, you will still see the old icon in Finder. This is due to the Finder icon cache, which only gets updated if certain files within the app have a new modified date. The icon file itself isn't one of them. In order to trigger Finder to update its icon cache, it is sufficient to update the modification time of two items by "touching" them from a Terminal:

touch /Applications/AppName.app
touch /Applications/AppName.app/Contents/Info.plist

Normally, this will be sufficient for Finder, but if the app is also in your Dock, you will have to restart the Dock: run this in your Terminal:

killall Dock

If you get errors about insufficient permissions, run each command with sudo in front of it to elevate your permissions.