Should a collection of constants be placed in a class or interface?

If they have strong connections, then I'd put them in an enum:

public enum Error {
  ERROR_1("-1", "foo went wrong"),
  ERROR_2("-2", "bar went wrong");

  private final String id;
  private final String message;

  Error(String id, String message) {
    this.id=id;
    this.message=message;
  }

  public String getId() {
    return id;
  }

  public String getMessage() {
    return message;
  }
}

The advantage is that you can have type safety in your code and that you can easily add id-based lookup (either by building a HashMap<String,Error> in the constructor or by simply looping over values()).

Some people consider constant-interface an anti-pattern (http://en.wikipedia.org/wiki/Constant_interface) .