Philip Nel

Yes, Harry is half-blood. We learn in SS4 that Lily's parents were Muggles.  At least, that's the implication of Aunt Petunia's remarks that they were proud having a witch in the family. Voldemort, too, is half-blood: we learn in CS2 that his father was a Muggle (his mother was a witch). The intense focus on whether or not a certain character does or does not have magical parentage (or on the degree of magical parentage) seems contrary to the novels' argument that what you do matters more than to whom you were born. That is, we learn time and time again that choices are more important than any innate qualities we may or may not have. As Dumbledore says at the end of CS, "It is our choices, Harry, that show us what we truly are, far more than our abilities."

If I may be so bold as to suggest it, the question that should be asked is not "is this character half-blood or pureblood?" but "what's the significance of asking such a question in the first place?"  That is, why does Rowling have certain characters care about magical parentage, when other characters do not care in the least?  What assumptions lie behind this concern over purebloods, half-bloods and "mudbloods"?

follow up:
by Caliburn

I've never fully understood why this seems to be a source of so much confusion--though I have noticed that there are some HP fandom sites that misrepresent this information, so perhaps that's why.

As Philip Nel has pointed out, canon indicates very strongly that Harry is considered a half-blood by whatever standard the Wizarding World uses. I would not be repeating this except for the fact that some people seem to still be confused, so I think we should bring out the relevant canon quotes:

CS17, The Heir of Slytherin
   [Tom Riddle to Harry]
   "There are strange likenesses between us, after all.  Even you must  have 
    noticed.  Both half-bloods[...]"

Of course it is certainly possible that Riddle may not be totally reliable, what with the future Lord Voldemort being the bastion of truth that he is.  (After all, cold-blooded murder is one thing, but a fib or over-generalization?  No, that's certainly where The Dark Lord draws the line.)  There is a certain logic to this, because we do have precedent in the Potter universe for statements that are false going unchecked in canon.  For example, JKR confirmed in an AOL chat that when Riddle said Hagrid was raising werewolf cubs under the bed, this was a lie--pure slander.

But we also have:

GF24, Rita Skeeter's Scoop
   [Hagrid to Harry]
   "I'd love yeh ter win, I really would.  It'd show 'em all . . . yeh don' have teh 
    be pureblood ter do it."

So unless Hagrid is also either lying or somehow misunderstands the criteria for 'blood status' (both of which seem highly unlikely), then we know Harry is not concerned a pureblood just because both of his parents are wizards.

And this then gives additional credence to Tom Riddle's statement in CS.

Since there is no conflicting evidence and one piece of consistent (though not strictly corroboratory) evidence, I recommend we take Riddle's statement at face value and assume Harry is a half-blood.

We can then assume that the criteria for half-blood status is not based on immediate parentage, but overall genealogy (as seems logical).  Exactly what standard the Wizarding World uses (one-drop, four/eight generations, etc.) is unknown and perhaps not consistent.