To answer your question as to whether Young Goodman Brown has blackness in his soul when he begins his journey, we only have to look at his farewell conversation with his wife, Faith, who implores him not to go on this journey at night:

"Poor little Faith!" thought he, for his heart smote him. "What a wretch am I to leave her on such an errand! She talks of dreams, too. Methought as she spoke there was trouble in her face, as if a dream had warned her what work is to be done tonight. But no, no; 't would kill her to think it. Well, she's a blessed angel on earth; and after this one night I'll cling to her skirts and follow her to heaven."

Brown's journey violates all beliefs and reason that he should be exercising at this point. First, a Puritan going unarmed and alone into the forest at night is an invitation to be killed by the Native Americans who not only live in the forest but are considered, by virtue of their "barbaric" nature, to be allied with Satan. A typical Puritan would not venture into the forest at night unless he has some ill intent. Brown's comment that "what a wretch am I to leave her on such an errand" speaks to what we now call "consciousness of intent"; that is, he knows this is a journey to his dark side.

Brown's reasons for this journey are never explicitly explained, but we can infer from his actions, as well as Hawthorne's comment that "Goodman Brown felt himself justified in making more haste on his present evil purpose," that Brown intends to seek evil on this journey. Hawthorne is also playing with the concept of Justification in the Puritan belief system, which is not a rational act of an individual but the gift of God by grace that saves a sinner. In Brown's decision, the word justified is synonymous with vindicated, excused, or permitted, another perversion of the belief system that Brown is prepared to violate in order to seek evil. The goal of a Puritan is to become a justified sinner, not an unjustified sinner.

That Brown understands the nature of this dark journey is clear from his reaction upon meeting his companion:

"You are late, Goodman Brown," said he. "The clock of the Old South was striking as I came through Boston, and that is full fifteen minutes agone."

"Faith kept me back a while," replied the young man, with a tremor in his voice, caused by the sudden appearance of his companion, though not wholly unexpected.

The arrival of his companion, "not wholly unexpected," scares Brown slightly, but not because it is unexpected—in fact, he is actually seeking Satan. Satan's physical presence is a part of the Puritan belief system, which holds that evil, in the form of witches and Satan, can manifest itself anytime it wishes. Just as evil ones appear in dreams, so they appear in life in physical, tangible, form. Brown and we recognize Satan because of a subtle detail he mentions: he has been able to walk from Boston, a day's journey by foot from Salem, in the space of fifteen minutes.

Brown's bitterness at the pervasiveness of evil begins when he sees a cloud passing overhead, apparently on its way to Satan's convocation, in which he perceives the voice of Faith and, more important, sees Faith's pink ribbon:

But something fluttered lightly down through the air and caught on the branch of a tree. The young man seized it, and beheld a pink ribbon. "My Faith is gone!" cried he, after one stupefied moment. "There is no good on earth; and sin is but a name. Come, devil; for to thee is this world given."

This, for Brown, convinces him that goodness has no place in this world, a conviction that is made stronger at the convocation when he sees Faith as a convert to Satan among a group:

"Faith! Faith!" cried the husband, "look up to heaven, and resist the wicked one."

Brown's warning to Faith does not include himself. Immediately after this scene, he finds himself alone in the forest and makes his way back to Salem where he finds everything, including his wife, tainted with evil.

His subsequent life is clouded by his "experience," and he shuns everyone, including Faith. When the family prays, Goodman Brown "scowled and muttered to himself, and gazed sternly at his wife, and turned away." Befitting a man who has turned his back on his belief system and exhibits nothing but despair, the worst of Christian sins, "his dying hour was gloom."

We know that when Goodman Brown sets out from his home he knows that he was doing something he ought not to do. When he considers whether a dream could have alerted his wife as to why he's going into the woods; he thinks,

But, no, no! 't would kill her to think it. Well; she's a blessed angel on earth; and after this one night, I'll cling to her skirts and follow her to Heaven.

If Brown were planning to do something totally innocent, then it wouldn't be so shocking to his wife so as to hurt her to know it. Further, Brown says, essentially, that he'll be good after just one more night of sinfulness. After this one last night of sin, he promises himself that he will follow his Faith—and his Christian faith—and adopt a path of goodness. Thus, he has already committed some sins, and he intends to continue to do so tonight; blackness does, then, exist in his soul even before he leaves home.

Goodman Brown begins to grow bitter on the next morning. The narrator wonders if Brown were only dreaming the witches' sabbath, saying,

Be it so, if you will. But, alas! it was a dream of evil omen for young Goodman Brown. A stern, a sad, a darkly meditative, a distrustful, if not a desperate man, did he become, from the night of that fearful dream.

Henceforth, Brown cannot listen to the congregation singing hymns; he pales when he hears the preacher sermonize; he shrinks away from a distrusts his wife, Faith; and he dies in "gloom." Brown's bitterness develops and overwhelms him the morning after his night in the forest, and, having lost his Christian faith, never recovers from it, and he is to blame. He is the one who makes the choice to abandon Faith (and faith), and it costs him everything.

Yes, I believe that Goodman Brown returns from the ceremony with darkness in his soul. 

The question is, as you have indicated, does he have the darkness in his soul before that time?

I think that you can see Brown's vulnerability to darkness in the first paragraphs of the story. To be specific, when Faith warns him not to go and Goodman insists on going anyway (paragraphs 2 and 3), that's a warning. Look at the characters' names. This is a case when a good man is ignoring the warnings of his faith. That's not good in any situation and, in a story about an explicitly Christian community, it's a clear symbol of impending fall (sin) due to pride.

This leads directly to an answer to your last question: yes, Goodman Brown definitely deserves blame for what happens. I'd say he deserves quite a bit of blame. Again, start with the story's opening: he refuses to listen to his faith. That's blameworthy in itself. If you include the fact that he (Goodman) rejects his wife Faith's concerns, he deserves even more blame.

This pride is underscored when he says, "What if the devil himself should be at my very elbow!" and then continues to walk the path. This is a man who decides to leave faith and go on expecting to encounter the devil. Since no man (in a Christian frame) can resist the devil without faith, he deserves blame.

As for when he becomes bitter, I'd argue that this change happens only in the last few paragraphs of the story. Before that, Goodman is wrapped in his arrogance. It isn't until that is punctured that the bitterness sets in.