This is the fundamental difference between this epic and The Iliad. The Iliad was an epic based on absolutes. If one was to be victorious, one would have to have a good heart, mind, body and soul. Every decision would have to be for good reasons, executed in a pure way, with no selfishness, in order to be blessed by the gods with success.
The Odyssey is based in moral relativistic setting. Lies could be told if an ultimate good would come from it. Odysseus is constantly lying, cheating and stealing for an ultimately good goal. He must commit small sins along the way in order to achieve the greater good.
This reflects real life. Our lives our full of gray decisions. Clear black and white choices are rare and we are constantly making compromises in order to achieve final (good) goals.
In Ancient Greece, their cultural norms are vastly different from our own. Odysseus demands that Penelope stay faithful for twenty years while he's off making love with beautiful goddesses like Calypso and Circe and he wasn't an unwilling prisoner/lover either. Women were viewed differently when this story was first orated. They were possession who were to do what they were told, they were to be faithful, they were to bear children (heirs). That's not to say they didn't love each other, but he never had a second thought about what he did because he was the king and it wasn't really cheating on his part because this was their cultural norm, which is why he never feels guilty over what he's done.
Odysseus is a warrior and warriors kill people. He didn't need to justify killing in the midst of battle. Even when he was killing the suitors, to him this was seen as a battlefield and he was defending his wife, his son, and his kingdom.
His biggest lie was his beggar disguise. He was warned by Athena that if he entered Ithaca straight away he, his family, and his kingdom might face trouble so we can see why he held this lie up, he also wanted to know if Penelope had stayed faithful.
Stealing to Odysseus was seen as collecting the spoils of battle. When he stole Polyphemus' sheep he was of the mind that he was owed because Polyphemus had eaten six of Odysseus' men. He saw it as "an eye for an eye" most literally.
I don't think anything really justifies it. He learns in the end that the gods control his fate. It's kind of a sub-topic, if you will, but the main point in the story is to prove to Odysseus that he isan't in control of his fortune, the gods are. Odysseus does these things like killing and stealing because he has not yet learned. Later he learns that he doesn't have the right to do that.