Afro Samurai, on Fuji TV (Japan) / Spike (USA)
ANN; IMDb; Madman; TV Tropes; Wikipedia
streaming sites: FUNimation; Hulu; iTunes; Vudu
Samuel L. Jackson provides the voice of both the title character and his travelling companion, Ninja Ninja. It's set in a world that has elements of both Feudal Japan and the future, I guess. There are also these two ancient headbands, Number One and Number Two. Whoever wears the number one headband rules the world, and whoever wears number two is the only person who can challenge number one to a fight. When Afro was a young boy, he watched his father fight, and get killed by, some guy called Justice (Ron Perlman). So now Justice wears the number one headband, and the story skips forward to Afro as an adult, now wearing the number two headband, and searching for Justice, to kill him, thus avenging his father's death.
Along the way, he'll have to fight lots of people, of course, including members of a cult called the "Empty Seven." Afro is followed around by an annoying guy called Ninja Ninja, who's kind of like a fan of Afro's, I guess. Though I had some suspicions about his true nature, and I think it turned out that I was right, but it wasn't exactly clear to me. There are also lots of flashbacks to when Afro was a kid, and some friends he stayed with and studied swordfighting with. They'll resurface in the present as enemies, and include a woman called Okiku (Kelly Hu), and a swordsman named Jinno (Yuri Lowenthal), who now wears a giant cybernetic teddy bear head.
Not sure what else to say. The show's okay, but I didn't like it quite as much as I'd hoped I would. The animation was pretty cool and the fights were awesome, but I had a bit of trouble following the story.
There's also a sequel movie called Afro Samurai: Resurrection.