Validation strategies

I am developing a search form and am wondering about the best way to perform validation.  I assume it is generally preferred to do Javascript validation to avoid doing round trips to the server just for validation.  However, if Javascript is disabled, there would need to be server side validation as well.  So is it worth writing the Javascript if I will just perform server side validation as well?

Also, I am a search form where the validation will require certain combinations of criteria are met.  For instance, either zip code, or state and zip, or other combinations of criteria must be met.  When I think of all the if then statements that will be necessary to perform this type of validation it just seems messy.  It seem I will certainly miss a combination in there somewhere.  Is there a strategy for doing this type of validation or are a ton of if then statements the only way?
...