Shortly after you begin the game you'll hear rumors about the Dark Brotherhood and how, when you murder someone, the Dark Brotherhood will visit you in your sleep. That's the key to joining -- you have to murder someone and then rest. So what's the big deal? You're going to be killing stuff throughout the game, after all. The problem is that critters don't count and the assorted Bandits, Marauders, Necromancers and other "bad guy" NPCs are exactly that: bad guys. Killing them doesn't count as murder. You have to find a non-bad guy and kill them. And who knows? Perhaps that non-bad guy that you just whacked might be helpful later on. Sounds like a dilemma, doesn't it?
Not so, my young apprentice. We want you to give in to the dark side, but we want you to do it on someone that you're going to have to kill anyway, who isn't a publicly known bad guy and who won't be screaming for the guards when you try to take him out (or at least not much). There are several very good candidates from other quest lines, so a little patience and creativity is all you need.
In the Arena faction you have to fight the Gray Prince in order to become the Grand Champion. If you complete his side quest before challenging him, he will just stand there and let you beat on him. It's not murder per se, but it draws the attention of those unkown forces just the same.
From the Mages Guild questline, you have four likely candidates that you are expected to get rid of in order to complete a quest: the vampire hunters in Skingrad. My advice on that quest was to let the vampires do the work for you, but you're perfectly welcome to do it yourself. Count Hassildor won't complain as long as they aren't in Skingrad anymore. The hunters will not be there until the "Information at a Price" quest is active, but you can certainly take out any or all of them. Vontus is relatively far away from town, so sniping him shouldn't present many problems. Carsten is outside the gate leading to the castle, so you can take him out without drawing unwanted attention. Shamar and Eridor both hang out in town, but it's possible to take both of them down without getting the guards involved. You'll know you've succeeded when you get the "Your killing has been observed by forces unknown" message.
From the Daedric quests, Clavicus Vile wants you to retrieve Umbra from the Vindasel ruin (which is a pretty good idea to do anyway). It took a lot of work, but I've managed to take her down at 1st level and every time that I've done it I've received the "Your killing has been observed by forces unknown" message.
From the Main Quest you have a bunch of Mythic Dawn agents scattered around in the towns. Cingor (a Wood Elf Crusader), Else God-Hater (a Nord Spellsword), Hans Black-Nail (a Nord Warrior), and Isolde (a Redguard Pirate) are all members of the Mythic Dawn faction, are not needed for any quests, are not publicly known to be bad guys, but will morph into Mythic Dawn assassins after the appropriate point in the Main Quest. There are undoubtedly others, but I haven't identified them yet. The problem with these folks is that they hang around in towns and it will be difficult to avoid the guards if you kill them in public. Of course you can always cough up the 1000 gold bounty when the guards show up, but I prefer to avoid that expense.
At any rate, once you have taken out your victim and received the "Your killing has been observed by forces unknown" message, you'll be contacted the next time you rest in a relatively isolated place. You'll be awakened by Lucien Lachance, who is the Speaker for the Dark Brotherhood. You'll have more dealings with him later in the questline, but for now he's there to offer you membership in his little "family". If you're interested in joining, you'll need to perform a real assassination.
Lachance tells you to kill Rufio, a guest at the Inn of Ill Omen on the road between the Imperial City and Bravil, and gives you the Blade of Woe with which to do the dirty deed. The blade itself is no great shakes to start with, but it's a quest item (which means you can't remove it from your inventory) and it will get better as you progress through the Dark Brotherhood questline. If you're not interested in joining, you can simply ignore the quest, but you're stuck with the blade. I should also note, for the sake of completeness, that Lachance is NOT essential. You can kill him if you want (he will fight back), but you'll close off the Dark Brotherhood questline if you do.
Rufio isn't hard to find (he's the only guest at the Inn) and Lachance was correct when he said that Rufio sleeps his days away. Rufio is only up and about between 2 a.m. and 6 a.m. The rest of the time he's asleep in his room. If you're not into killing NPCs in their sleep, you can wake him up first and probably find out that Rufio is a murderer and (possibly) a rapist on top of that. But either way he's a 1st level character and should go down quickly. You do not need to use the Blade of Woe on him; any weapon will do. Once Rufio is occupying some other plane of existence, Lachance will visit you the next time you rest and give you more instructions. You might also note that your Infamy has gone up one point.
You should be aware that where each successful quest for the Fighters Guild and Mages Guild netted you a boost to your Fame, each successfully completed contract for the Dark Brotherhood will boost your Infamy. In and of itself it's no big deal unless you let it get ahead of your Fame. In that instance you'll be locked out of any healing from the Chapels and cannot use any Wayshrines. You'll also find that at least some NPCs will behave differently with you. Because of these drawbacks, I try to make sure that I've got a good cushion of Fame before I ever start on the Dark Brotherhood questline and have even gone so far as to complete the Thieves Guild questline and let the Gray Fox take the Infamy hit. I'm probably being unnecessarily cautious, but a little caution goes a long way toward heading off problems later.
On an added note, the "Knights of the Nine" official mod keeps track of your Infamy. If it ever gets above one, you won't be able to use any of the nifty gear you're collecting. Moral of the story: do the Dark Brotherhook before taking on the Knights mod or else do it when you don't need the gear anymore. The only other alternative is to spend a lot of time making pilgrimages to clear your Infamy.
Lachance sends you to the abandoned house in Cheydinhal with instructions to talk to Ocheevo, the local guildhall steward. If you progressed far enough in the Thieves Guild questline, you went to the house next door for a meeting with the Gray Fox. Although you'll be able to use a different entrance later, for the time being you'll have to enter the guildhall through the basement of the abandoned house and Lachance gives you the password that will let you in ("Sanguine, my brother"). The first time that you talk to Ocheevo, she'll give you your Dark Brotherhood armor, which has small but nice boosts to some of the stealthier skills (you'll get 10 points each to Sneak, Illusion, Blade, Marksman and Acrobatics; 2 points from the hood and 8 points from the armor), and she'll direct you to Vicente Valtieri for contracts.
Yes, Valtieri is a Vampire (if the pointy canines and red eyes weren't enough of a clue). He's not interested in your blood so much as he's interested in your services as an assassin and he will be your source of contracts for the next few quests. One of the odd things that happens with the Dark Brotherhood is that you'll get an active quest notice as soon as the previous quest is completed; unlike the other factions where you actually have to start a quest to activate it. The short version of what you'll see is "I need to ask Valtieri for a contract." Once that's done the next quest will activate.
There are others wandering around the guildhall who have interesting conversation topics and can provide useful advice on how to deal with particular contracts. One odd-ball thing that I've noticed with the Dark Brotherhood is that each time you complete a quest, everyone's "Rumors" topic lights up again, but they don't have anything new to say. It never hurts to use it just to be sure, but don't be surprised to hear the same things over and over again. M'raaj-Dar seems to dislike you just on principle, but will sell you useful stuff and otherwise behave like any other merchant. He doesn't have any different conversation threads, so you'll get the same abuse, insults and attitude even with his Disposition at 100.