Will adding the "Nofollow" tag in the affiliate link structure hurt the onpage SEO?

That's probably a question only you can answer. Depends on the affiliations, what type of site you're running, etc.

I ask this question because I have added the "Nofollow" tag in all my affiliate links and I observed a huge decreasing of search engine rankings.

When did you add the nofollow? Did you do anything else prior to that or after that? If adding nofollow "was the only thing you did" and nothing else, then we may be able to say that was the cause of the effect.

I'm still not convinced that the nofollow attribute is something you'd want to use outside of a community posting environment. Originally, that nofollow was a vote of "no trust". If you have to use nofollow on your partner links then something may not be Kosher at home.

If you implemented the nofollow a few months ago and your partners saw that and did the same, then it appears that this whole nofollow thing may work? ;)

echoing what P1R said and

ask yourself why did you originally put Nofollow in place - you didn't trust destination page, wanted to 'hog' PR, because everyone else was doing it ( :) ), etc. - what is your specific reason?

depending on your answer, you can accomplish similar things with redirect (but make sure you ban redirect script in robots.txt). Depending what you are trying to accomplish there are pros and cons to both approaches. Nice thing about redirect method is that you can collect data for 'link clickthrough' stats....

shand0, did your rankings drop in G, Y and MSN? If some but not all of the major engines, which?

We use nofollow all over the place for pr shaping without penalty.

See this interview question of matt cutts for more clarification:

Does Google recommend the use of nofollow internally as a positive method for controlling the flow of internal link love?

* A) Yes – webmasters can feel free to use nofollow internally to help tell Googlebot which pages they want to receive link juice from other pages
_
(Matt's precise words were: The nofollow attribute is just a mechanism that gives webmasters the ability to modify PageRank flow at link-level granularity. Plenty of other mechanisms would also work (e.g. a link through a page that is robot.txt'ed out), but nofollow on individual links is simpler for some folks to use. There's no stigma to using nofollow, even on your own internal links; for Google, nofollow'ed links are dropped out of our link graph; we don't even use such links for discovery. By the way, the nofollow meta tag does that same thing, but at a page level.)