A good way to explain this entails first understanding what the respective trees were - and why partaking of one of them immediately caused them to feel shame, or guilt, and to view each other, and God, differently. But because you did not ask about those trees (only the resulting shame at realising their nakedness), I can only make a few bald statements which space will not permit me to enlarge upon, given that the question is about clothes and not trees.
With regard to clothing, Genesis 2:25, "they were both naked and felt no shame". The NIV Study Bible (1987 edition) has a note which says "Freedom from shame, signifying moral innocence, would soon be lost as a result of sin - see 3:7." Also, verses 10 & 11 use the same word as in verse 7, very slightly different, but likewise meaning the same thing. Those last three occurrences of what is translated "naked" only became associated with shame after they had disobeyed God.
This is why knowing what they did is crucial to grasping why they then felt shame. Here is the concluding point on this, from a book that takes many pages to explain the symbolism of the tree of the knowledge of good and evil:
"The tree itself represents righteousness. But not the same
righteousness [as represented by the tree of life]. Another
righteousness. For there are two standards of righteousness, and two
ways of righteousness, from one end of the Bible to the other. And two
The first has been shown to signify the righteousness of faith, that
is, the righteousness of God by faith of Jesus Christ... there is only
one other way of righteousness: it is the righteousness of the law.
This must be attained by works commensurate and consistent with its
Such a legal standard gives no righteousness; rather, it gives the
knowledge of righteousness, commanding good and prohibiting evil. It
is therefore the knowledge of good and evil, and requires works equal
to the rectitude which it describes...
Therefore, dimly, in the most veiled symbol - as was the tree of life yet in essential principle, the tree of knowledge of good and evil set forth the righteousness of the law, or, in a word, the concept of
It was not in man in innocence, and it is not in man in the Fall, to
find anything in the righteousness of the law save the exceeding
sinfulness of sin, and the unalterable cursing of death. 'Now we know
that what things soever the law saith, it saith to them who are under
the law: that every mouth may be stopped, and all the world may become
guilty before God' Romans 3:19." Creation, pp 151-154, John Metcalfe
To be innocent is to be free from guilt. To know guilt - which is hand in glove with shame - is to have lost innocence. That is why the couple instantly felt shame, as expressed in their feeble attempt to make fig-leaf coverings for themselves, and to hide from God. Their clean consciences had become sullied by their act of disobedience. They wanted to cover-up and to hide. From God. "For by the law is the knowledge of sin" - Romans 3:20. This new-found knowledge was knowing experientially what sin was. They had sinned against God, their Maker, lost their innocence, felt shame, and wanted to cover-up and hide.
That, I suggest, is what this concept of nakedness is in Genesis 2 & 3.