Is "Happy Birthday!" a complete sentence? And if it is, what role are the words happy and birthday playing? Where is the verb? Can "happy" be a verb? I know in a sentence like "Go get the milk" there is an implied "You" at the beginning that makes it complete. Is there an implied verb?
There are those who consider statements which do not consist of complete sentences as always wrong. While sentence fragments and other sentence substitutes (see http://www.thefreedictionary.com/sentence+substitute ) should not be used where lack of clarity would result, and their overuse is bad style, strings such as 'Happy Birthday(!)', 'No', 'Thanks', 'Ciao', 'On the table', 'Up the Reds', 'Too bad!' etc are commonly used and not wrong per se. Some are formulaic (eg 'On yer bike!') and, even if they are elided forms, that might now be hard to deduce. Less formulaic examples are usually more obviously elided forms (Where are the keys? - (They are) On the table.)
You could consider 'Happy Birthday' to be an elision of 'You have a happy birthday' via 'Have a happy birthday', but the phrase stands well enough alone (and has achieved double-capital-letter status as a fixed expression of salutation). As Janus Bahs Jacquet says in his comment, “Happy Birthday!” is not a sentence according to the normally accepted definition. But that does not make it unacceptable (as is usually quite obvious when it is used).
In ‘The Cambridge Encyclopedia of the English Language’, David Crystal distinguishes between major sentences and minor sentences, as follows:
‘[A major sentence] is a type of sentence which is highly productive, such as those with a subject plus predicate structure; contrasts with minor sentences, where there is limited productivity, or where the structure lacks some of the constituents found in the major type.’
On that basis, ‘Happy Birthday’ is a minor sentence.
'Happy birthday' is a shortened form of Have a happy birthday. 'Merry Christmas' is a shortened form of have a merry Christmas. 'Good day' is a shortened form of have a good day. These are all expressions, and as expressions, they don't have to be true sentences in order to be inserted into text.