Vou acrescentar uma outra abordagem ao que já foi dito.
O que é um padrão de projeto e a [não] relação com OOP.
Padrões de arquitetura ou padrões de projeto, os famosos design patterns, de forma bem objetiva, tem um papel facilitador para executar tarefas repetitivas que já possuem soluções conhecidas que são consideradas adequadas para determinadas situações.
Orientação a objeto
Não precisa ter uma relação direta com orientação a objetos. Padrões de projeto estão em tudo o que você faz na programação em qualquer paradigma.
Em alguns padrões de projeto isso é mais necessário em linguagens orientadas a objetos. Os padrões servem para resolver problemas que a própria linguagem criou ou problemas que a linguagem não consegue lidar bem. Normalmente isto é feito criando regras, modelos, receitas de código que usados daquela forma atingem um objetivo.
Padrões estão em todo lugar
Mas é preciso entender que existem padrões de projeto que não são assim. Existem padrões nas bibliotecas. O que é até melhor porque você não precisa saber como implementar este padrão de projeto, tem que saber apenas como usar as ferramentas disponíveis na biblioteca. A grosso modo apenas tem que saber como chamar e como usar o resultado de uma ou mais funções ou métodos.
Infelizmente o termo design patterns ficou famoso apenas para o primeiro caso. E para piorar, as pessoas acham que esses padrões famosos encontrados em livros e sites são solução para tudo. Acham que tudo pode ser resolvido com um padrão existente. Os programadores e gerentes de projeto abusam de algo consagrado porque não entendem bem o que estão fazendo. Perguntar sobre casos específicos sobre o assunto pode ir ajudando entender melhor em casos específicos.
Existe ainda uma outra forma de padrão de projeto muito comum e existente há décadas. São as construções de linguagem.
Construções de linguagem
Então, por exemplo, variável é um padrão de projeto que ninguém acha que é porque está aí há tanto tempo. Raramente é ensinado como ela funciona concretamente e as pessoas não conseguem enxergá-la como um padrão, principalmente porque a linguagem disfarça bem. E fica mais complicado vender livros, palestras e consultorias de algo tão importante, mas também tão pronto para ser usado.
Funções são design patterns, assim como métodos que já é um padrão em cima de outro padrão que está implementado em cima de diversos outros padrões. Operadores também são.
Statements como if
, for
, while
, for each
, etc. são outros exemplos.
Valores, referências, expressões, e claro, classes são todos padrões de projeto. Ninguém pensa muito como usá-los como padrão de projeto.
Tem linguagens que ensinam como implementar o padrão observer, tem linguagens que possuem este padrão implementados como eventos.
Quando o padrão está tão enraizado na sua mente você acha que não está usando um padrão de projeto. Eu conheço programador que não pensa mais sobre o uso do MVC. Aquilo é tão normal para ele que não parece ser um padrão (outros porque não entendem o que está fazendo, só "ensinaram-me assim"). Mas podemos dizer que sempre escolhemos um padrão em tudo.
A maioria dos padrões são muito bons quando usados no momento certo, sejam eles parte da linguagem, biblioteca ou receita de bolo.
Como escolher um padrão
Alguns padrões são determinados ou influenciados pelas tecnologias que você escolheu. Embora nem sempre precise segui-los. É comum seguir o que foi determinado para uma tecnologia. Profissionais muito bons e com conhecimento profundo naquela tecnologia escolheram o que seria mais adequado em cada caso. Mas eles podem errar. Eles podem propor algo ótimo para a maioria dos casos mas que não seja o ideal para você em determinada situação.
Você pode criar um novo padrão
É possível mas é improvável que ele seja melhor do que os existentes. Claro que isto depende do que você está fazendo. Em domínios específicos pode ser que você crie um padrão que pelo menos não foi publicado como um caso conhecido e comprovado.
Ovo ou galinha?
Há casos que você pode determinar o melhor padrão para uma tarefa e ir à caça da tecnologia que melhor atende sua necessidade. Deveria, mas isso não é tão comum.
Experiência, sempre ela
Você deve aproveitar o que outros mais experientes fizeram antes ou sua experiência anterior. Deve aprender com essas experiências. Só não deve ficar cego e considerar que todo padrão de projeto que aparece é bom para tudo.
Seus exemplos
MVC
Eu, por exemplo, nunca trabalhei ativamente com web, faço basicamente aplicações desktop. Sempre que posso, pelo menos mais recentemente (no passado eu usava padrões que eram bons para a necessidade da época e que nem tinham nome, mas hoje são considerados arcaicos) procuro usar MVC (ou algo parecido) e minhas aplicações são stateful. Então não há uma relação direta que foi citada como uma possibilidade para seu uso. O motivo para se usar o MVC está destacado abaixo.
Hoje quase todo mundo concorda que precisa usar um padrão de interação com o usuário que o modelo de dados precisa estar separado do comportamento que manipula a interação com o usuário. Existem alguns padrões que fazem isto. Uso o MVC porque se adapta bem ao que eu preciso e já é bem usado com as tecnologias que tenho adotado.
MVC está muito associado com UI. Embora nada impeça de fazer de outra forma, praticamente qualquer API para UI é exposta utilizando técnicas de OOP. Provavelmente UI é a aplicação mais adequada para OOP. Portanto o padrão MVC e OOP acabam tendo uma uma relação próxima nos casos comuns.
Alguns padrões se encaixam melhor em alguns paradigmas, sendo quase inviáveis usando outro paradigma. Por outro lado alguns padrões são tão adequados a um paradigma que muitas vezes você acha que não está usando padrão algum. O paradigma impõe determinados padrões intrinsecamente, em oposição a recomendar uma receita de bolo.
Se eu for usar WPF, por exemplo, vou ver melhor como funciona o MVVM. Mas não é porque a Microsoft diz que é bom que eu vou usá-lo. Dá muito bem para usar WPF sem MVVM. Eu sei que o projeto fica mais simples se não usá-lo, e isto é uma grande vantagem. Mas ainda não sei tudo o que eu perco com isto. Certamente tem alguma perda, sei de pelo menos uma. Vou ter que fazer uma escolha. Vou contar com minha experiência. Não tem outro jeito. Por isso que você vê na internet um monte de gente amando e odiando esta tecnologia (só para ficar neste exemplo). Cada um tem uma experiência diferente.
Conclusão
Aprenda os padrões, mas principalmente aprenda suas vantagens e desvantagens, em detalhes. Aprenda quando usá-los e quando evitá-los.
Coloquei no GitHub para referência futura.