OOP-Design for validating user input

The validator in your example doesn't have a state (and doesn't need any), but another validator could require one (say with a format):

Example:

public class RegExValidator {
    private Pattern pattern;
    public RegExValidator(String re) {
        pattern = Pattern.compile(re);
    }
    public void validate(String input) throws ValidationException {
        if (!pattern.matcher(input).matches()) {
            throw new ValidationException("Invalid syntax [" + input + "]");
        }
    }
}

Concentrating on the OOP aspect of your question (rather than the question if an Exception is the correct way to handle your validation):

Why have a single validator?

interface Validator<T> {
    void validate(T toValidate) throws ValidationException;
}

would enable you to write classes that can validate any class T and be very testable. Your validator would look like this:

class EmptyStringValidator implements Validator<String> {
    public void validate(String toValidate) {
        if(toValidate == null || toValidate.isEmpty()) throw new ValidationException("empty!!!");
    }
}

and you could test it very easily. In fact, if you're using Java 8, this would be a functional interface, so a single utility class could host several validators:

class ValidationUtil {
    public static void emptyString(String val) // same code as above
}

and ValidationUtil::emptyString would implement Validator<String>. You would combine several validators with a composite pattern.

You could also have a validator with a state if that's what you need...

class ListIsSortedValidator implements Validator<Integer> {
    private int lastInt = Integer.MIN_VALUE;
    public void validate(Integer val) throw ValidationException {
        if (val < lastInt) throw new ValidationException("not sorted");
        lastInt = val;
    }
}

That you could use to for instance validate a list:

List<Integer> list = createList();
Validator<Integer> validator = new ListIsSortedValidator();
list.forEach(validator::validate);

It depends on the circumstances of course, but I think your instinct is correct. This design could be more Object-Oriented.

It is not just that Validator has no state, which is a purely mechanical indicator that it is likely not a correct abstraction, but the name itself tells us something. Usually Validator (or even EmptyStringValidator) is not part of the problem domain. It is always a bad sign when you have to create something purely technical (although sometimes it is the less of two evils).

I assume you are not writing a web-framework, you are trying to write an application that has some domain. For example it has user registration. Then, RegistrationForm is part of the problem domain. Users know about the "registration form", you can talk about it and they will know what you mean.

In this case, an Object-Oriented solution for validation would be that this object is responsible for the validation of itself during the "submitting" of itself.

public final class RegistrationForm extends Form {
    ...
    @Override
    public void submit() {
        // Do validation here
        // Set input fields to error if there are problems
        // If everything ok do logic
    }
}

I know this is not the solution normally seen or even supported by web-frameworks. But it is how an Object-Oriented solution would look like.

The two important points to always keep in mind are:

1. Don't "get" data from objects, ask them to do something instead. This is as applicable to UI code as anything else.
2. OO makes sense when the objects focus on meaningful things, i.e. the problem domain. Avoid over-representing technical (unimportant) objects, like Validator (if that's not your application's domain).