How to validate forms properly? Some useful dos and donts

Nothing worse than when you have to click submit to find out that the username is taken, and now you have to retype the passwords and the captcha again, to also find the other one is taken too..