This is explained in the book. Snape's mother's surname was Prince. Hence, he was a 'half-blood' Prince (not of royalty, just of the family Prince):
'I was going through the rest of the old Prophets and there was a tiny announcement about Eileen Prince marrying a man called Tobias Snape, and then later an announcement saying she'd given birth to a-'
'-murderer,' spat Harry.
'Well...yes,' said Hermione, 'So...I was sort of right. Snape must have been proud of being "half a Prince", you see? Tobias Snape was a Muggle from what it said in the Prophet.'
'Yeah, that fits,' said Harry. 'He'd play up the pure-blood side so he could get in with Lucius Malfoy and the rest of them.'
Half-Blood Prince Chapter 30: "The White Tomb"
(Quote courtesy of DavidS' Answer)