Spotify automatic startup mystery
A lot of functionality, like login items, extensions/kexts, LaunchAgents or other Helpers can be packed into the application bundle these days.

If you look closely at the content of the Spotify.app, by right- or control clicking it and selecting "Show Package Contents", you'll find a "Library" folder enclosed in the Content's folder.  Within it there is a LoginItems folder, containing the login item.
    /Applications/Spotify.app/Contents/Library/LoginItems/StartUpHelper.app/Contents/MacOS/StartUpHelper

This "StartUpHelper" will launch Spotify at login.  This seems to be the application's default behaviour.

You wrote:


  Otherwise it would start for every new user added to the system.


I certainly have seen Spotify auto-launch on a user created after it had been installed, logging out of the user that created the new account and setting up the new user account from the login screen (alternatively two restarts were needed for Spotify to launch at login in the new user account). Only when Spotify got installed after the user was created, did it not launch at login.

A test in an attempt to explain, why some users will not see the auto-launch of Spotify at login:

I created and set up a new user before Spotify was installed on a different user account and, after Spotify was installed (again in a different user account), tried several logouts/logins and restarts to make sure it didn’t auto-launch at login for this new user. I also noted the user’s DARWIN USER DIRECTORY running the following command...
getconf DARWIN_USER_DIR

I also had a user for whom Spotify auto-launched at login every single time.  Again I noted the user’s DARWIN USER DIRECTORY.
Logged into this last mentioned user I quit Spotify and deleted...com.apple.LaunchServices-231-v2.csstore ...from the Darwin User Directory. Then I copied the same file from the other user’s Darwin User Directory (for whom Spotify didn’t auto-launch at login) over to this user’s directory (in Finder, to make sure the file’s owner would also change).

Then I logged out and rebooted several times into the user, for whom Spotify did auto-launch, but the behaviour stopped and Spotify refrained from launching.

PS. For further in depth information on login items within an application bundle, I’d suggest signing up for a free Developer account and getting acquainted with (some of) the documentation on application design (you don't have to sign up though, just to read the documentation).