You need to start an X terminal and give it the command you want to run as parameter. There probably is already a line to start a terminal in the icewm menu file, try copy-pasting that and addind -e <command> at the end of it.
Gdm runs ~/.xsession when you log in, so you can add commands there. However, a better way to start icewmbg is icewm-session, which starts all icewm-related programs at once. You need to find out where gdm stores the list of available window managers and replace icewm with icewm-session there. I don't use graphical login myself, so I don't know where it is.