It's probably best to make the icon some 'standard' size, like 32x32 or 64x64 pixels. Png's are good, since they can contain alpha channels to make the icon 'see through' in the parts you don't want it to block the background. Apparently .svg's are also supported, which are in vector format, and therefore scale infinitely.
The window managers have agreed on a free desktop standard for specifying icons using .desktop files. So if your app's executable is called 'foo', in that same directory you can have a 'foo.desktop' file that tells the window manager what icon to use, as well as other information about your executable (such as what description text it should show if the user hovers over it, etc).
In case the above links go stale, here's an example .desktop file:
[Desktop Entry] Version=1.0 Type=Application Name=Foo Viewer Comment=The best viewer for Foo objects available! TryExec=fooview Exec=fooview %F Icon=fooview MimeType=image/x-foo; X-KDE-Library=libfooview X-KDE-FactoryName=fooviewfactory X-KDE-ServiceType=FooService
..and here's a snapshot of the freedesktop 1.1 draft's description of the .desktop fields.