Is there something higher (better) than the word premium, or does it mean the best? Also, is there something in between premium and deluxe?
Graphically: Does any word fit here? > Premium > Does any word fit here? > Deluxe
Neither "premium" nor "deluxe" has a precise meaning (unsurprising, since they are both words in advertiserese, where precise meanings are undesirable because somebody might try and hold you to them), so there is no answer either to what order they come in, or to what you can put between them.
Colin is absolutely correct that "premium" doesn't really have a precise meaning. It is used in marketing to imply a somewhat better than baseline quality. There are loads of other such words, but which actually means a better product than which others is almost entirely up to the company's marketing department.
And of course "plus" added onto any of the above to knock it up another notch.
I think the only thing I've seen that definitively means "best" is "Ultimate". I wouldn't put it past a marketing guy to invent "Ultimate plus" though...
Premium does not mean the best. It simply means better.
Definition 10: of exceptional quality or greater value than others of its kind; superior: a wine made of premium grapes.
Deluxe, in this context, means "High or highest in quality", according to the dictionary, though it is held in more esteem than premium.
If you want to say the best, in most cases you can just say the best.
However, here is a list of synonyms, for if you ever want to wax eloquent:
beyond compare, capital, champion, chief, choicest, culminating, finest, first, first-class, first-rate, foremost, incomparable, inimitable, leading, matchless, nonpareil, optimum, out-of-sight, outstanding, paramount, peerless, perfect, preeminent, premium, prime, primo, principal, sans pareil, second to none, super, superlative, supreme, terrific, transcendent, ultimate, unequaled, unparalleled, unrivaled, unsurpassed
In between premium and deluxe? It would be hard to pin any word incontrovertibly between the two, especially since they are not generally used in the same contexts (ever seen deluxe grapes?) I came up with choice, superior, and exceptional.
If it's goods that you're talking about, top-grade implies that a product is the absolute best of a particular type of item.
Some etymology to back up what the other answers are telling you:
Premium as an adjective only dates from 1928, I suspect by someone who thought it was related to "primary". As a noun it actually derives from the Latin praemium, a profit made from booty, which seems disturbingly fitting for an advertising weasel word.
Deluxe has a full century on premium, and literally means what you might expect: "of luxury."
Neither of these words have much of an ordering of strength, so you can take them as you will.
I can't think of an intermediate term, but I like acme for "the best". Then again, I'm not Wiley Coyote...
Zenith technically means the point directly overhead but is used generally to mean the highest achievement of something.