It's a bit of a 'how long is a piecce of string set up' -
for an artist as big as Bowie, his Press Agent will approach a number of select magazines, papers, TV shows etc. and agree to which Mr Bowie will grant access. The agreement may include a front cover guarentee, a certain length of time at certain times of day for TV, and so on.
The arrangement is mutually beneficial, so it's highly unlikely that either side will pay the other directly. However, it may be agreed that a series of ads will be bought from a publication for the album - music papers make their money from advertising in the main.
If the interview is a genuine 'exclusive'. then the NME wold be delighted to get it, but Press Officers have a far wider audiencce demographic to work with, so total one-off exclusives are few and far between - more likely is an exclusive per demographic area - so for instance 'Q' may get an interview, and 'The Word' may not. The 'Sunday Times' may have an interview on the understanding that 'The Observer' doesn't, and it's usually carved up like that.
It does depend on the desirability of the aritst as to who would like to get into the 'exclusive' areas - Bowie is an excellent example, Morrisey would be another, bt a band like Iron Maiden, who are still massive, are more likely to do a 'scatter-gun' approach and talk to everyone.