A good breakdown of the story can be found here.
http://www.chabad.org/parshah/article_cdo/aid/683491/jewish/Why-did-Adam-and-Eve-become-aware-of-their-nakedness-only-after-they-sinned.htm
Basically, they were moving from a state of innocence to a state of personal responsibility. Before eve ate the apple, they knew there were correct decisions and there were incorrect decisions. That was not the same as having an evil inclination from within.
You can tell a child that something is bad and something is good. That doesn't mean they have this understanding of evil or a perception of this tug of war between their evil inclination and divine aspirations.
Adam and Eve were created in pureness so their nakedness was not an act of impurity or immodesty. Much like how nudity to a small child isn't the same as to an adult. A small child will strip off their diaper and run around naked while laughing maniacally but not have any evil or impure connections to that behavior (an example from the article). They do not do such things for impure reasons (such as a person exposing their body for sexual gratitude)
Adam and Eve gained an awareness of nudity and an awareness of their desire to turn away from G-d. This desire meant they were awakened to the other forms of desires which can be abused and be self-destructive. It was the point in which that tug of war (honoring G-d or turning away from G-d) started within all beings.
Nudity isn't inherently wrong, just as man and his wife having a loving sexual relationship in the nude is in no way evil. The problem is when nudity and sexuality get abused and lead to self-destructive tendencies which distract you from G-d and your personal responsibilities.
That is why nudity is associated with an awareness of good and evil in the Torah. Nudity sparks sexual desire and sexual desire sparks impure thoughts and impure thoughts (if exacerbated) can lead to self-destructive tendencies and away from G-d. Thus, we cover our bodies as an act of modesty and respect.
The same can be said for almost every behavior which there are laws.
Eating a delicious meal isn't wrong. Eating too much leads to gluttony which leads to self-destruction.
Drinking wine in celebration of Shabbos isn't wrong. Drinking too much can lead to falling into alcoholism which leads to self-destruction.
Hopefully that makes sense.