There is a video on youtube by Matt Cutts about this from a few months back.
It seems to me (and I have watched that video several times) that if your site loses rankings due to the algorithm, then if you change your site so that it should rank better, then it will do so the next time googlebot crawls it and has time to reindex the SERPs.
If, on the other hand, you have a manual penalty (a google employee went to your site and saw something suspicious), then you would have to fix it and submit a reconsideration request.
The video didn't clearly state that there would be a fixed time length to the penalty even if you fixed your site.
Lots of people on this forum have experience with getting their sites back after a penalty (I don't personally, since I don't appear to have ever been penalized - knock on wood). You might search these forums for OOP or the words over optimization penalty
I think the more important question is WHY do you think you have been penalized?
If you search for a unique string of text on your page, is it showing up at number 1 in the serps? (Or at least very close to the top of the SERPs?)
Were you getting lots of inbound links? Doing any cloaking?