I have a cross platform program that runs on Windows, Linux and Macintosh. My windows version has an Icon but I don't know how to make have one for my Linux build. Is there a standard format for KDE, Gnome etc. or will I have to do something special for each one?
My app is in c++ and distributed as source so the end user will compile it with gcc.
If I can have the icon embedded directly inside my exe binary that would be the best.
For Gnome and Kde, you would probably want to include a desktop file with your app that defines how it will be launched. The specification can be found here. If you have an installer included with your app, you would probably want to have it generate this desktop file and put it in the right places to make menu entries and whatnot
KDE community with it's KDE 4 series started to use CMake as a build system. They developed a CMake macro that knows how to set an icon for your application regardles of the platform (windows (embedded in exe), mac (.app bundles), linux (.desktop files) etc.)
Maybe you can use it.
If you are using one of the pre-baked F/OSS build systems, such as KDE's CMake support, it's really rather easy once you have a .desktop file:
install( FILES myapp.desktop DESTINATION ${XDG_APPS_INSTALL_DIR} ) kde4_add_app_icon(myapp_SRCS "${CMAKE_CURRENT_SOURCE_DIR}/hi*-app-myappname.png")
If you are rolling your own, consider using xdg-utils, which includes handy little scripts like xdg-desktop-menu (installs desktop menu items) and xdg-desktop-icon (installs icons to the desktop) for such things.
The .desktop standard was already pointed out in the first comment, though you can also just grab one that is already installed on your system and modify it from there. As for icons, PNGs and SVGs are geerally supported though PNGs tend to give the best results still.