Which X session are you using? I use KDE. In your home directory, there is a file called .kde and then a directory called Autostart. Place your startup programs (like xmms) in that Autostart folder. You must have hidden files viewable to see the . folders.
In GNOME, what I do is close down GNOME with the application I want to autostart (like rhythmbox) running. If your session preferences are checked to save your session on logout, then whatever apps are open on shutdown will open again when GNOME is started. Once you have GNOME the way you want it to start, go into the session preferences and uncheck the box for saving your session on logout.
I use KDE regularly, so the GNOME directions are only from my memory of months ago. The KDE directions I checked. Hope it all works out!