Na empresa onde trabalho, estamos criando uma nova arquitetura de sistemas foi me solicitado que criasse um pequeno exemplo usando essa arquitetura, com as classes Cidade, Estado, etc.
A princípio, o design mais comum seria o de criar uma superclasse comum (ex. "Região") e a partir dela herdar cada uma.
No entanto, IMHO, não é uma resposa tão óbvia, já que uma Cidade "é um" Região mas também "é um" divisão política.
Talvez, nesse caso, fosse mais interessante usar Interface.
Alguns links para estudo:
http://guj.com.br/posts/list/87814.java
http://blog.caelum.com.br/2006/10/14/como-nao-aprender-orientacao-a-objetos-heranca/
http://www.datasuldirect.com.br/flash/JAVA_SC/Or_Obj.pdf
UPDATE (11/08)
Mais um post interessante sobre o mesmo assunto:No, inheritance is not the way to achieve code reuse!