right to the point:
What makes an album as a "deluxe version"? People may notice that they usually have some bonus tracks. But, what makes them deluxe other than that?
It's really just a marketing term, similar to 'Special Edition', 'Collector's Edition', and so on. It could potentially be anything that the record company wants the consumer to believe provides added value. An extra remix CD or live DVD, limited edition artwork booklet... thicker vinyl / gold CD... or, as The Smiths tell us in Paint A Vulgar Picture: Double-pack with a photograph, Extra track, and a tacky badge...
Wikipdia has a general page called Special Edition, which also contains a good definition of Deluxe Editions.
In terms of musical albums, the term "deluxe edition" refers to a re-release of an album, generally a sufficient period after the initial release, featuring extra content related to the album. This often includes some or all of the following: extra tracks; demo recordings of album tracks; live recordings of album tracks; alternate takes, mixes, or edits of album tracks; B-sides from album singles that did not appear on the album; DVD content, including music videos. These editions are commonly repackaged, with the new content on a second disc and many feature additional liner notes.
Also, some albums are initially released in two editions, a regular retail version and a "special" or "limited" version in distinctive packaging and often including extras such as a second disc, a video DVD, or liner notes expanded into a hardback book. Generally, the special package is only produced for the first pressing or a set number of copies - some are limited to only being sold at one chain of retailers. It is important to distinguish this from an expanded re-release, since those are generally available widely and for a long period of time.
So, a Deluxe Edition is typically, but not always, released after the origninal album. Also, it most probably features some extra material to make people buy it.
Additionally, the page has the following definition:
The terms special edition, limited edition, and variants such as deluxe edition, collector's edition or expanded edition, are used as a marketing incentive for various kinds of products, originally published products related to the arts, such as books, prints, video games or recorded music and films, but now including cars, fine wine, and whisky, among other products.
So, it is definitely a marketing "trick" as well. The record companies know that record buyers are interested in extra material, and are willing to pay for it.
Finally, I just cannot resist quoting Morrissey here:
Re-issue! Re-package! Re-package!
Re-evaluate the songs
Double-pack with a photograph
Extra track (and a tacky badge)