Why is Lust a sin in Matthew, but praised in Proverbs? Jesus says in the gospel of Matthew [paraphrasing] "if you look at a woman and lust for her, you have already sinned in your heart."  

In proverbs, they say, [again, paraphrasing] "let her [the companion of your youth] breasts satisfy you."  

Is that not lust?  Aren't these two messages contradicting each other?
The context of Matthew is adultery--relations with a woman who is not your wife.  The context of Proverbs is marriage--relations with the woman who is your wife.  The difference is quite substantial.

“You have heard that it was said, ‘You shall not commit adultery.’ 28 But I say to you that everyone who looks at a woman with lustful intent has already committed adultery with her in his heart.  Matthew 5:27-28 ESV
Let your fountain be blessed,
And rejoice in the wife of your youth.
19 As a loving hind and a graceful doe,
Let her breasts satisfy you at all times;
Be exhilarated always with her love.  Proverbs 5:18-19 NAS

God actually created sexual intimacy to be fully enjoyed within the marriage relationship.  Adultery, however, is a corruption of that holiest of relationships which destroys intimacy.  Thus, it is strictly forbidden in both thought and deed, for our own good.
So, there is no contradiction at all.