Like CraigR said, your initial option should have a value attribute set to a blank string:
<option value="" selected="selected">Select A State</option>
Then use required validation on the state select list.
Neilo: with the differences in how browsers handle form elements lately, i have found that some browsers will not pass a form element if it does not have a value attribute set. I have seen this happen for text elements, checkboxes and even select lists.
because of this, I would not recommend using select lists that do not have the value attribute, even if the value is the same as the label.