Una classe definisce oggetti "immutabili" quando lo stato dell'oggetto non può più essere modificato dopo che l'oggetto è stato creato. Per essere più precisi/pignoli, dall'esterno l'oggetto non deve "mostrare" alcun cambiamento di stato. Infatti l'oggetto internamente potrebbe anche avere dello stato mutabile (caso eccellente: String che è immutabile ma il campo hash è calcolato on-demand la prima volta che hashCode() è invocato, quindi questo è mutabile ma questo aspetto non traspare all'esterno).
Quindi: niente metodi che cambiano lo stato, nessun metodo "setter". Campi non visibili all'esterno e possibilmente final (non è tanto il final che forza la immutabilità di per sé ma aiuta su aspetti legati al threading).
E se vogliamo andare oltre: classe final, cosa che perlomeno evita che qualcuno la estenda aggiungendo stato mutabile.