The following is largely informed by Dr. Iain Provan's lectures on Genesis at Regent College.
As always in Hebrew narrative, it's helpful to look for repetition to understand each passage in context. The themes of nakedness and knowledge run throughout the whole sequence of events:
- They are naked but without shame, suggesting a certain innocence.
- The serpent is "crafty" (a wordplay on "naked" in Hebrew, perhaps the opposite of innocence).
- They eat from the Tree of the Knowledge of Good and Evil.
- They become aware that they are naked and attempt to cover up.
- They are afraid of God because they are naked and so they hide from God.
- God asks who told them they were naked and concludes that they ate from the tree.
- God helps them cover up better.
Putting up walls
From this sequence it seems that nakedness is not shameful. However, when people become aware of their nakedness, they become self-conscious. It's implied that this consciousness is, or at least is associated with, the "knowledge of good and evil".
Once conscious of nakedness, the people become afraid — perhaps of being seen, thus of being known. In other words, they feel they have something to hide. And they do have something to hide: their disobedience. They hide their bodies because they feel exposed. Physical nakedness stands in for spiritual nakedness.
So they put up a wall that divides Adam from Eve, and worse, both of them from God. The relationship of openness is broken. Indeed, this seems to have been the serpent's aim — his first question, "Did God really say ...?" and his follow-up, "God lied to you," are calculated to undermine the people's trust in God. By getting them to hide from God, the erosion of trust is completed.
Of course, there is no hiding from God. God sees through the walls they put up. This comes to the ashamed Adam and Eve as something frightening, because now they have to own up to their disobedience, but in the big picture it's good news for us. We can make believe we're hiding from God, but God is still able to reach us. He calls us out into the open (cp. John 3:20-21), where he spells out the consequences for our actions, but he also hints that the future will be different.
You also asked: Why fig leaves? Provan reads it as a jab at how inexperienced the humans are at covering up. This is their first time, after all. Sewing leaves together doesn't make for great clothing. Right after making said clothing, they still perceive themselves as naked! They then go on to respond to God in a way that sounds like a child caught doing something they know they shouldn't, but not yet aware that they can lie. They're bad at covering up their spiritual nakedness as well.
God, however, takes pity on them and modifies his plan to accommodate for human stubbornness — as he does repeatedly in the Bible (e.g. Mosaic law, the institution of monarchy). He gives them more effective clothing so they don't have to feel naked. Since God sees the heart anyway, the improvement in covering up makes little difference to their already fractured relationship, but it's a comfort to Adam and Eve.
When God accommodates, he doesn't just treat it as a stopgap measure, but he incorporates the change into his plans for the long run. Jesus comes to fulfill the law rather than to abolish it. The metaphor of the kingdom and the Davidic line of kings directly contributes to our understanding of Jesus' role. And in the visions in Revelation, people are clothed in white. :)