Embedding an icon in a Linux executable

On Ubuntu:

mouse right click the icon you don't like -> Properties -> in the opened window click the icon -> choose an icon you want

Executables on Linux do not have icons embedded (try to point your file manager to /usr/bin). What you have seen is probably a Desktop Entry. That's a text file describing the icon, program name and the executable.