Como sempre, depende. E isso pode ser de acordo com sua aplicação ou se terá endereços só brasileiros ou de fora também.
Existe basicamente três abordagens:
- Deixa o endereço completamente livre, provavelmente com várias linhas, e o usuário é responsável por colocar certo. Muito usado em alguns países dada a complexidade.
- Tenta ser o mais estruturado possível tendo um campo para cada tipo de dado que o endereço possa ter. Raramente usado porque é complexo e difícil atender todas as expectativas.
- Algum nível híbrido sendo mais simples e flexível, mas também sendo um pouco mais organizado.
No Brasil no mínimo costuma-se separar cidade, estado e CEP, e eventualmente o bairro. É raro fazerem, mas pode ser bem útil, mas tem casos que separa o tipo de logradouro, a informação principal do logradouro, o número e um complemento(s). Para ficar melhor teria que permitir mais dados, ou pelo menos que um dos complementos fosse bem livre para pôr o que quiser, o que perde um pouco da organização nesse nível. Até a cidade pode ser complicado resolver porque tem organizações intermediárias entre cidade e bairro.
Se só aceitará endereços no Brasil facilitaria um pouco porque muita coisa não existe aqui.
É muito difícil saber a hora de parar de estruturar e começar deixar mais livre.
Lembre-se que é um assunto muito difícil e tem muitos mitos sobre o assunto. Então tentar fechar todas as questões pode ser bem complicado. Por exemplo o endereço pode ser só uma caixa postal e você não ter acesso a mais nada. Pode ser que seu sistema não aceite isso, mas pode ter que aceitar, e todo o resto, fora o CEP não é uma informação disponível. Pense nisso.
Pense que tem caso que só tem uma descrição de onde fica a localização, não tem um endereço estruturado, e isso pode ser válido em várias situações. É assim que cartinha para o Papi Noel chega ao destino. Em muitos lugares de zona rural, comunidades pouco estruturadas ou situações precárias são alcançadas. Já viu um endereço de Brasília? è o oposto da estruturação.
Obviamente que descrições mais próximas podem ser menos estruturadas. Se tiver toda uma informação interna de um condomínio, é claro que a informação é útil, mas ela não precisa ser tão estruturada assim, servirá mais para quem for fazer uma entrega chegar mais fácil, muitas vezes até delegando pra alguém que conhece melhor ali dentro.
Um dado que muita gente não percebe como parte do endereço, porque ele não é totalmente, mas é usado para a mesma finalidade, é descrição do local, o "como achar mais facilmente o local" que pode ser útil durante a entrega. Este deve ser mais livre. E pode ter como complementos, apontamento geográfico, e imagens de mapas e fotos do local ou passagens importantes. Claro que pode ser algo mais sofisticado no sistema, mas pense nisso. O objetivo do dado determinará o que fazer.
Lembre-se que endereço é descritivo, qualquer parte dele, não faz contas com ele. Ainda mais que quase tudo que você acha que só tem algarismos pode ter letra e você não sabe ainda. Tem lugares que seguem numeração de blocos e o número interno ao bloco.
Se o dado segue um padrão, se tem uma lista possível, não deixe o usuário digitar, ou valide o que ele digitou. Mas se fechar o cerco demais pode inviabilizar algum caso excepcional. Se quiser ser pedante crie um subsistema de criticidade que seja rígido e permita a flexibilidade. Tem organização que pode ter alguém para avaliar o preenchimento de dados, principalmente quando tem excepcionalidade. Em muitos casos ele é muito importante.
Nem entrei na questão de precisar ter endereços diferentes para situações diferentes ou o que fazer quando muda o endereço (cuidado porque informações antigas podem precisar do endereço antigo) Veja aqui e aqui e também.
Já pensou que o endereço está sendo usado cada vez de forma automatizada em outras aplicações que não entendem entrada de qualquer jeito?
Cuidado com "APIs" que ajudam a achar dados de endereço e CEP, muitos são bem falhos e entram resultados errados, porque é difícil acertar de forma tão automática.
Existe um lugar que tenta colher um conjunto dos mitos que as pessoas possuem sobre o assunto.
Tem quem tentou juntar informações que ajudam entender tudo o que deve ser considerado no mundo, mas não é algo completo e definitivo.
Essas informações podem ser úteis para formatar o dado quando usar em algum lugar, até capitalização tem regra, que vão além do escopo da pergunta.
Coloquei no GitHub para referência futura.