Introdução
Quase sempre os sistemas operacionais permitiram funcionar assim. Claro que alguns não o fazem, mas não precisa ter vários processadores, físicos ou lógicos, para que vários processos ou mesmo threads possam rodar "ao mesmo tempo".
Há ganho em fazer isso sempre que existe estado de espera por alguma razão. Seja porque o hardware está manipulando dados por ele próprio, seja porque a própria aplicação está em estado de espera. Então limitar a quantidade de linhas de execução traria prejuízos já que nada estaria sendo feito durante essas pausas.
Seria mais fácil mas não seria o ideal. A dificuldade foi o preço que resolveu-se pagar para aproveitar melhor os recursos disponíveis. A ideia é manter o processador ocupado.
Colocar mais processadores não resolve isso. O motivo está explicado em É sempre garantido que uma aplicação com múltiplas threads rode mais rápido que usando uma única thread?.
Agendamento
Há um sistema de agendamento que é um algoritmo específico de sistemas operacionais para ir dando controle do processador para cada linha de processamento existente. O sistema operacional deixa uma linha executar por um tempo e depois há uma interrupção que devolve o controle do processador para o sistema operacional que poderá decidir em seguida o que fazer com o processador.
Isso é feito com instruções específicas do processador que cria a interrupção na execução depois do tempo estabelecido pelo sistema operacional. A interrupção é como um evento que muitos conhecem em alto nível, só que é controlado pelo hardware.
Esses algoritmos começam com a criação de listas de linhas de execução que são pedidas através da API de processos de threads. De acordo com as configurações o sistema operacional alocará um processador para aquela linha, podendo trocá-la seguindo alguns critérios, e um tempo específico (poucos microssegundos) para que ele execute até que retorne para o sistema operacional. Esse tempo pode variar de acordo com a quantidade de linhas existentes.
O SO fica em um laço e quando recebe o controle de volta ele entrega para outra linha de execução. A frequência que uma linha é chamada pode ser controlada também algum SOs, então não é preciso que todas linhas existentes executem uma vez para voltar executar outra vez.
Tudo isso depende da implementação de cada sistema e das condições do ambiente que está executando.
Alguns usam algoritmos bastante sofisticados para dar o melhor resultado possível para cada situação.
Pense nele como um guarda de trânsito ou um semáforo inteligente. Bom, tecnicamente um semáforo básico já é uma boa analogia, só que os SOs costumam ser melhor que isto.
Isso é a multitarefa preemptiva. No passado alguns SOs usam a multitarefa cooperativa. Não havia a interrupção, então o SO contava com a boa vontade da aplicação de devolver o controle para ele. Isso travava tudo se a aplicação "enroscasse". Com o hardware ajudando e o SO usando a preempção a aplicação não pode se apoderar do processador. A instrução de configuração interrupção só é acessível pelo SO.
Existem sistemas operacionais de tempo real que precisam dar mais garantias sobre a execução.
Obviamente isto é um resumo para leigos.
Artigo da Wikipedia sobre o assunto.
Coloquei no GitHub para referência futura.