I believe that there are multiple types of Herobrine. The first one is, obviously, the mod. I hear there is also a mob in the X-Box version. I think there are a few hackers that mess around with multiplayer servers. There's probably a virus too, the one that goes into singleplayer worlds. I think the ghost version is a stupid story to scare people.
I've been studying Herobrine, and have found out that all versions seem to like mines, and that the mod supposedly reads the Minecraft forums. In the mod, he seems to talk of victory and killing you, as well as haunting your dreams and breaking into your house. The hackers (supposedly) seem to use cheats and communicate through the chatbox. They also sometimes take control of players, lagging their Minecraft. They also seem to hack stuff like lava that doesn't completely fall and entire structures. The virus seems to dig 2 by 2 block tunnels into random mountains, put traps in caves, and create ocean pyramids. It also seems to block e-mails to Mojang about it, and sometimes even replies. I don't know much about the X-Box one, except that it supposedly traps you in a coffin sometimes (made of blocks, as their are no coffins in any version of Minecraft).
Notch said he had a dead brother that he never knew that passed away, but then a year later confessed that is was just to spread word of Herobrine, and did not have a dead brother.
The first time Notch put "Removed Herobrine" into the updates, it meant he removed the non-player "Steves" in the game (known as "Humans" or "Monsters"). The rest of the time, as stated in the Minecraft Wiki, Jeb was making a joke. (By the way, think about this. How could you remove something more than once?
That is all the research I have gathered on Herobrine, and will continue to search for more.
PS. I'm not registered, so I couldn't put any links.